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:
Contest has ended. No further submissions allowed.
- 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