31400번 - 헤네시스 오솔길 (Hard) 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 86 | 21 | 20 | 36.364% |
문제
헤네시스 오솔길의 좌우로 늘어진 길이 $4L$의 필드에 주황버섯이 $N$마리 있습니다. 이 주황버섯들은 모든 버섯들의 어머니와 같은 존재, 머쉬맘의 명령을 받고 모였습니다.
처음에 $i$번 주황버섯은 필드의 왼쪽 끝에서 $4P_i+1$만큼 떨어진 곳에 있으며, 주황버섯은 정해진 왼쪽 혹은 오른쪽 방향을 바라보고 있습니다. $(1 \le i \le N)$ 주황버섯은 매 초마다 다음 규칙을 따라 이동합니다.
- 주황버섯은 자기가 바라보는 방향으로 $1$만큼 이동합니다.
- 이동 후에 같은 위치에 있는 주황버섯이 두 마리 이상이라면, 모여있는 모든 주황버섯은 다음 시각부터 방향을 바꿔 반대 방향으로 이동합니다.
- 주황버섯이 필드 끝에 도달한다면, 주황버섯은 필드에서 벗어나게 됩니다.
머쉬맘은 아래의 상황에서 주황버섯들에게 방향을 바꿀 것을 명령할 수 있습니다.
- 모든 주황버섯이 움직이기 전인 $0$초 째에.
- 주황버섯 한 마리가 필드를 빠져나갈 때.
머쉬맘이 명령을 내리면 모든 주황버섯들의 이동 방향의 좌우가 바뀝니다.
머쉬맘은 주황버섯들을 이끌고 헤네시스를 침공하려고 합니다. 따라서 헤네시스가 있는 방향인 왼쪽으로 빠져나가는 주황버섯의 수를 최대화하고 싶습니다. 필드의 왼쪽 끝에서 빠져나오는 주황버섯 수의 최댓값과, 이 때 어떤 방식으로 명령해야 하는지 출력하세요.
$L$ 과 $P_i$가 정수라면 어떤 시점이든 두 마리 이상의 주황버섯이 한 번에 필드를 빠져나가거나, 주황버섯이 필드를 빠져나갈 때 두 마리 이상의 주황버섯이 만나는 경우가 없다는 것을 증명할 수 있습니다.
입력
첫 줄에는 주황버섯의 수 $N$과 필드의 길이와 관련 있는 정수 $L$이 공백으로 구분되어 주어집니다. $(1 \le N \le 200\,000;$ $1 \le L \le 10^8)$
다음 $N$개의 줄의 $i$번째 줄에는 주황버섯의 위치와 관련 있는 정수 $P_i$와 주황버섯의 진행방향을 의미하는 문자 $C_i$가 공백으로 구분되어 주어집니다. $(0 \le P_i \lt L)$ $C_i$가 L인 경우 주황버섯이 처음에 왼쪽 방향을, R인 경우 주황버섯이 처음에 오른쪽 방향을 보고 있다는 의미입니다. 처음에 중복되는 위치에 있는 주황버섯은 존재하지 않습니다.
출력
첫 줄에 필드의 왼쪽 끝으로 빠져나오는 주황버섯 수의 최댓값을 출력하세요.
둘째 줄에 머쉬맘 명령의 횟수 $K$를 출력하세요. $(0 \le K \le N+1)$
$K$가 양수인 경우, 셋째 줄에 $0$ 이상 $N$ 이하의 서로 다른 $K$개의 정수를 공백으로 구분하여 출력하세요.
- $0$을 출력한 경우, 모든 주황버섯이 움직이기 전인 $0$초째에 머쉬맘이 명령합니다.
- $i$를 출력한 경우, $i$번 주황버섯이 필드에서 빠져나간 이후 명령합니다. $(1 \le i \le N)$
정수를 출력하는 순서는 상관 없으며, 정답이 여럿인 경우 아무거나 하나 출력하세요.
예제 입력 1
4 5 1 L 3 R 4 R 2 L
예제 출력 1
2 0
예제 입력 2
4 7 1 L 3 R 4 R 2 L
예제 출력 2
4 5 0 1 2 3 4
출처
Contest > solved.ac > solved.ac Grand Arena #4 > Division 1 F번
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호