¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8017
Subtarea

가로등 2s 1024MB

Problemas

수직선 도로 위에 N개의 가로등이 켜져 있다. 각 가로등의 위치는 왼쪽부터 차례대로 A_1 \lt \cdots \lt A_N 로 나타낼 수 있다.

위치 x의 어두운 정도를, 그 위치로부터 가장 가까운 가로등까지의 거리로 정의하다. 이는 N개의 수 |A_1 - x|, \cdots,|A_N-x| 중에서 가장 작은 값과 같다. 여기서 |\cdot|는 절댓값 기호로, y\ge0이면 ,|y|:=y, y \lt 0이면 |y|:=-y이다.

예를 들어, N=3개의 가로등이 차례대로 A_1 = 1, A_2 = 4, A_3 = 8에 위치한다면, 0부터 10까지 각 정수 위치의 어두운 정도는 다음과 같다.

위치

0

1

2

3

4

5

6

7

8

9

10

어두운 정도

1

0

1

1

0

1

2

1

0

1

2

가로등이 있는가?

O

O

O

x=0부터, x=L까지 L+1개의 정수 위치의 어두운 정도를 모두 계산했을 때, 가장 작은 값부터 K번째로 작은 값까지 차례대로 출력하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다. 

  • 1 ≤ L ≤ 1,000,000,000,000,000,000  

  • 1 ≤ N ≤ 300,000  

  • 1 ≤ K ≤ 500,000  

  • K ≤ L + 1  

  • 0 ≤ A_1 < A_2 < \cdots < A_N ≤ L 


Entrada

첫 줄에 세 정수 L, N, K가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 N 개의 정수 A_1, \cdots , A_N이 공백으로 구분되어 차례대로 주어진다.


Salida

첫 줄부터 K 개의 줄에 걸쳐 답을 출력한다. 이 중 i 번째 줄에는 i 번째로 작은 어두운 정도의 값을 출력한다.


Subtarea

# Puntaje Condición
#110

N = 1

#220

N \le 2,500, L \le 2,500

#315

2 \le N. N-1은 L을 나눈다. A_i = \frac{L}{N - 1} \times (i - 1) 

#420

L \le 5,000,000

#535

추가 제약 조건 없음.


Ejemplo #1

10 3 4
1 4 8
0
0
0
1

Ejemplo #2

4 5 5
0 1 2 3 4
0
0
0
0
0

Ejemplo #3

7 1 4
3
0
1
1
2

Ejemplo #4

9 4 10
0 3 6 9
0
0
0
0
1
1
1
1
1
1


Fuente

2024 KOI 2차 초2/중1/고1

Debes iniciar sesión para escribir código.