폭격

시간 제한7초메모리 제한1024 MB

요약

남은 점을 가장 많이 덮는 정수 중심을 매번 고르고, 동점이면 가장 작은 중심을 고르는 과정을 시뮬레이션합니다. 선택한 중심을 순서대로 출력합니다.

난이도: 보통10점 중 7점
유형: 그리디, 슬라이딩 윈도우, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

게임 Bombardment의 목표는 폭격으로 점들의 집합을 파괴하는 것이다. 테마는 아직 정해지지 않았고, 핵심 규칙은 폭격이다.

점은 실수 수직선 위에 있으며, 각 점은 x좌표 하나로 주어진다. 폭격은 정수 $X$ 를 중심으로 하며, 구간 $[X-R, X+R]$ 에 있는 모든 점을 파괴한다.

대부분의 테스터는 탐욕 전략을 쓴다. 각 폭격은 그 시점에 가장 많은 점을 파괴하도록 고른다. 그래서 최소 횟수보다 많은 폭격을 쓰는 경우가 생긴다. 이 전략을 시뮬레이션하는 프로그램을 작성한다.

과정은 다음과 같다. 남은 점이 있는 동안, 남은 점을 가장 많이 파괴하는 폭격의 중심 $X$ 를 고른다. 최댓값을 주는 중심이 여러 개이면 가장 작은 $X$ 를 고른다.

입력

첫 줄에 두 정수 $N$ ( $1 \leq N \leq 5 \times 10^5$ )과 $R$ ( $1 \leq R \leq 10^8$ )이 주어진다. 다음 줄에는 점들의 x좌표 $N$ 개가 주어지며, 각 값은 $[-10^8, 10^8]$ 범위에 있다. 같은 x좌표를 가진 점이 여러 개 있을 수 있다. x좌표의 최댓값과 최솟값의 차이는 최대 $40 \cdot R$ 이다.

출력

첫 줄에 폭격 횟수 $B$ 를 출력한다. 둘째 줄에는 수행한 순서대로 $B$ 개 폭격의 x좌표를 출력한다.

예제4

예제 1
입력
```
7 1
1 2 3 3 4 4 5
```
예상 출력
```
3
3 0 4
```
예제 2
입력
```
6 1
5 -2 5 0 1 2
```
예상 출력
```
3
1 4 -3
```
예제 3
입력
```
6 2
5 -2 5 0 1 2
```
예상 출력
```
2
0 3
```
예제 4
입력
```
6 3
5 -2 5 0 1 2
```
예상 출력
```
2
2 -5
```