Problem G

You are designing an old-school game you call Bombardment where the goal is to destroy a number of points by bombarding them. You do not yet know the theme of your game, just that the core mechanics should involve a bombardment.

The points to be destroyed are located on the real number line, that is each point is simply an $x$-coordinate. A bombardment is an attack that will destroy all points within some fixed distance $R$ from the center of the bombardment. More specifically, a single bombardment is specified by picking an integer point $X$ (the center). All points lying in the interval $[X-R, X+R]$ will be destroyed.

You decide to playtest a basic version of this game before you go through the effort of designing a theme, adding nice graphics, etc. Interestingly, most testers seemed to employ a greedy strategy: each bombardment is chosen to destroy the maximum number of points in that single bombardment. Sometimes, this causes players to use more bombardments than the minimum possible number of bombardments. You want to design a program that will simulate this strategy, this will help you design interesting levels.

That is, your job is to write a program that will simulate the following process. While there are still points remaining, choose a value $X$ for a bombardment that will destroy the maximum number of remaining points. If there are multiple values $X$ for the center of such a bombardment, you will choose the least such $X$ each time.


The first line of input contains two integers $N$ ($1 \leq N \leq 5 \times 10^5)$ and $R$ ($1 \leq R \leq 10^8$). The next line contains $N$ integers describing the $x$-coordinates of the points, each lying in the range $[-10^8, 10^8]$. Multiple points may share the same $x$-coordinate. You are also guaranteed that the difference between the maximum $x$-coordinate and the minimum $x$-coordinate is at most $40 \cdot R$.


The first line of output contains a single integer $B$ indicating the number of bombardments that were performed. The second line consists of $B$ integers describing the $x$-coordinates of each bombardment in the order they were performed.

Sample Input 1 Sample Output 1
7 1
1 2 3 3 4 4 5
3 0 4
Sample Input 2 Sample Output 2
6 1
5 -2 5 0 1 2
1 4 -3
Sample Input 3 Sample Output 3
6 2
5 -2 5 0 1 2
0 3
Sample Input 4 Sample Output 4
6 3
5 -2 5 0 1 2
2 -5

Please log in to submit a solution to this problem

Log in