시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 72 | 19 | 12 | 37.500% |
세린이는 세상에서 가장 커다란 극장인 세린극장의 오너이다. 세린극장에는 왼쪽부터 순서대로 $1$번부터 $N$번까지의 번호가 붙은 총 $N$ 개의 좌석이 있으며, 그 중 $M$ 개의 좌석인 $P_1, P_2, \cdots, P_M$번 좌석은 온라인상으로 예약이 되어 사람들이 이미 도착해 있다.
세린이는 남은 모든 좌석의 표를 오프라인상으로 팔기로 하여, 현재 $N-M$ 명의 손님이 표를 사기 위해 도착해 있다. 모든 손님은 현재 남아있는 좌석 중 가장 쾌적한 좌석에 앉고 싶어 하며, 좌석의 쾌적함은 자신으로부터 가장 가까운 사람이 멀수록 높다. 구체적으로, 표를 사고 새로 들어가는 $i$ 번째 사람이 가장 쾌적하다고 느끼는 자리는 다음과 같다:
- 자신이 앉았을 때 가장 가까운 사람과의 거리가 가장 먼 자리
- 그런 곳이 여러 개라면, 다음 사람이 들어와서 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리
- 그런 곳이 여러 개라면, 그다음 사람이 들어와서 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리
$\vdots$
- 그런 곳이 여러 개라면, $(N-M-i)$ 번째 다음으로 들어온 사람이 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리
- 그런 곳이 여러 개라면, 번호가 가장 작은 자리
오프라인 상으로 표를 사러 온 첫 $K$ 명의 VIP 손님에게는 세린이가 직접 손님들을 안내하고 싶었다. 하지만, 세린극장에는 좌석이 너무 많아 세린이는 손님을 어느 좌석으로 안내해야 할지 알 수 없다. 여러분이 세린이를 도와 손님들을 가장 쾌적한 좌석으로 안내해주자.
첫 번째 줄에는 $N, M, K$가 공백으로 구분되어 주어진다.
두 번째 줄에는 $P_1, P_2, \cdots, P_M$이 공백으로 구분되어 주어진다.
$K$ 개의 줄을 출력한다. 이 중 $i$ 번째 줄에는 $i$ 번째로 들어가는 사람에게 안내해 주어야 하는 자리의 번호를 출력한다.
5 1 4 3
5 1 2 4
10 1 9 6
1 10 8 4 2 3 5 7 9
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2021! G번