P4364 [Nine-Province Joint Exam 2018] IIIDX

Have you heard of Osu? That is Konano’s favorite rhythm game, and his dream is to make a unique and cool music game of his own someday. Now he works at the world-renowned game company KONMAI, getting closer to his dream. A music game usually contains many songs; the more songs, the less likely players get bored. Meanwhile, to make players spend ~~more money~~ more time on the game, not all tracks are available from the beginning. Some tracks are unlocked only after you clear a specific track, and the later a track is unlocked, the higher its difficulty tends to be.

Konano received a task to arrange the unlock order of tracks for the in-development game “IIIDX.” There are $n$ tracks in total. Each track has a difficulty $d$. The $i$-th track is unlocked after the player clears the $\left\lfloor \frac i k \right\rfloor$-th track ($\left\lfloor x \right\rfloor$ is the floor function). If $\left\lfloor \frac i k \right\rfloor = 0$, then this track requires no unlock. For example, when $k = 2$, the $1$-st track requires no unlock ($\left\lfloor \frac 1 2 \right\rfloor = 0$), and the $7$-th track is unlocked after the player clears the $3$-rd track since $\left\lfloor \frac 7 2 \right\rfloor = 3$. Konano’s job is to arrange the order of these tracks so that each newly unlocked track has a difficulty not lower than the prerequisite track’s difficulty. That is, after determining the order, the difficulties satisfy $d_i \geq d_{\left\lfloor \frac i k \right\rfloor}$ for every $i$. Of course, this is easy for Konano, who has spent a lot of time “chilling” in informatics competitions. If it were you, how would you solve this task?

The first line contains one positive integer $n$ and one real number $k$. $n$ is the number of tracks, and $k$ is as described above. The second line contains $n$ space-separated positive integers $d$, representing the difficulties of the $n$ tracks.

Output one line with $n$ integers: the difficulty of the $i$-th track after arranging the order. If there are multiple valid solutions, output the one with $d_1$ maximized; if still tied, maximize $d_2$; and so on.

| Test point ID | $n$ | $k$ | $d$ | Special constraints | |-|-|-|-|-| | $1$ | $1 \leq n \leq 10$ | $k=2$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $2$ | $1 \leq n \leq 10$ | $k=3$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $3$ | $1 \leq n \leq 10$ | $k=1.1$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $4$ | $1 \leq n \leq 10$ | $k=n$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $5$ | $1 \leq n \leq 10$ | $1 < k \leq 100$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $6$ | $1 \leq n \leq 10$ | $1 < k \leq 100$ | $1 \leq d \leq 100$ | All $d_i$ are distinct | | $7$ | $1\leq n\leq 2000$ | $k=2$ | $1\leq d\leq 10^9$ | All $d_i$ are distinct | | $8$ | $1\leq n\leq 2000$ | $k=2$ | $1\leq d\leq 10^9$ | None | | $9$ | $1\leq n\leq 2000$ | $k=3$ | $1\leq d\leq 10^9$ | All $d_i$ are distinct | | $10$ | $1\leq n\leq 2000$ | $k=3$ | $1\leq d\leq 10^9$ | None | | $11$ | $1\leq n\leq 2000$ | $1 < k \leq 10^9$ | $1\leq d\leq 10^9$ | All $d_i$ are distinct | | $12$ | $1\leq n\leq 2000$ | $1 < k \leq 10^9$ | $1\leq d\leq 10^9$ | None | | $13$ | $1\leq n\leq 500000$ | $k=2$ | $1\leq d\leq 10^9$ | None | | $14$ | $1\leq n\leq 500000$ | $k=3$ | $1\leq d\leq 10^9$ | None | | $15$ | $1\leq n\leq 500000$ | $1