USACO 2022 January Contest, Platinum

Problem 1. Minimizing Haybales


Contest has ended.

Log in to allow submissions in analysis mode


Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has $N$ ($1\leq N \leq 10^5$) stacks of haybales. For each $i\in [1,N]$, the $i$th stack has $h_i$ ($1\le h_i\le 10^9$) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:

  • If two adjacent stacks' heights differ by at most $K$ ($1\le K\le 10^9$), she can swap the two stacks.

What is the lexicographically minimum sequence of heights that Bessie can obtain after some sequence of these operations?

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ and $K$. The $i+1$-st line contains the height of the $i$-th haybale.

OUTPUT FORMAT (print output to the terminal / stdout):

Please print out $N$ lines, the $i$-th containing the height of the $i$-th haybale in the solution.

SAMPLE INPUT:

5 3
7
7
3
6
2

SAMPLE OUTPUT:

6
7
7
2
3

One way that Bessie can swap the stacks is as follows: 

   7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3

SCORING:

  • In 10% of all input cases, $N\le 100$
  • In another 20% of all input cases, $N\le 5000$
  • In the remaining 70% of input cases, there are no additional constraints

Problem credits: Daniel Zhang and Benjamin Qi

Contest has ended. No further submissions allowed.