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.*

Problem credits: Daniel Zhang and Benjamin Qi

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

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

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

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > January > Platinum