페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4955

극장 좌석 배치 8s 1024MB

문제

세린이는 세상에서 가장 커다란 극장인 세린극장의 오너이다. 세린극장에는 왼쪽부터 순서대로 1번부터 N번까지의 번호가 붙은 총 N 개의 좌석이 있으며, 그 중 M 개의 좌석인 P_1, P_2, \cdots, P_M번 좌석은 온라인상으로 예약이 되어 사람들이 이미 도착해 있다.

세린이는 남은 모든 좌석의 표를 오프라인상으로 팔기로 하여, 현재 N-M 명의 손님이 표를 사기 위해 도착해 있다. 모든 손님은 현재 남아있는 좌석 중 가장 쾌적한 좌석에 앉고 싶어 하며, 좌석의 쾌적함은 자신으로부터 가장 가까운 사람이 멀수록 높다. 구체적으로, 표를 사고 새로 들어가는 i번째 사람이 가장 쾌적하다고 느끼는 자리는 다음과 같다:

  • 자신이 앉았을 때 가장 가까운 사람과의 거리가 가장 먼 자리

  • 그런 곳이 여러 개라면, 다음 사람이 들어와서 앉았을 때  자신과 가장 가까운 사람과의 거리가 가장 먼 자리

  • 그런 곳이 여러 개라면, 그다음 사람이 들어와서 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리

    ......

  • 그런 곳이 여러 개라면, (N-M-i) 번째 다음으로 들어온 사람이 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리

  • 그런 곳이 여러 개라면, 번호가 가장 작은 자리

오프라인 상으로 표를 사러 온 첫 K 명의 VIP 손님에게는 세린이가 직접 손님들을 안내하고 싶었다. 하지만, 세린극장에는 좌석이 너무 많아 세린이는 손님을 어느 좌석으로 안내해야 할지 알 수 없다. 여러분이 세린이를 도와 손님들을 가장 쾌적한 좌석으로 안내해주자.​ 


입력

첫 번째 줄에는 N, M, K가 공백으로 구분되어 주어진다.

두 번째 줄에는 P_1, P_2, ..., P_M이 공백으로 구분되어 주어진다.​ 

  • 1 ≤ N ≤ 10^{18}

  • 1 ≤ M ≤ 1,000,000

  • 1 ≤ K ≤ 1,000,000

  • K≤ N-M

  • 1 ≤ P_i ≤ N (1 ≤ i ≤ M)

  • P_i != P_j (1 ≤ i < j ≤ M)

  • 입력으로 주어지는 모든 수는 정수다.


출력

K 개의 줄을 출력한다. 이 중 i 번째 줄에는 i 번째로 들어가는 사람에게 안내해 주어야 하는 자리의 번호를 출력한다. 


예제 

5 1 4

3
5

1

2

4

출처

dennisstar
로그인해야 코드를 작성할 수 있어요.