P10392 [Lanqiao Cup 2024 NOI Qualifier A] Sealed Gems

During an adventure, the hero Xiao Lan found $n$ gems shining with a strange light. Each gem contains magical energy, denoted as $a_1, a_2,\cdots, a_n$. Xiao Lan plans to use $n$ special magic boxes to seal these gems, to prevent their magical energy from being misused. Sealing gems consumes Xiao Lan’s stamina. Specifically, putting the $i$-th gem into the $j$-th box costs Xiao Lan $i - j$ stamina points (note: to put the $i$-th gem into the $j$-th box for a valid seal, it must satisfy $j \le i$). Xiao Lan may also choose to leave boxes empty, saving stamina for later use. In addition, to avoid magic conflicts, each box can hold at most one gem (and each gem can be put into only one box), and any two adjacent boxes cannot contain gems with the same magic value. Adjacent boxes are allowed to be empty at the same time. Xiao Lan’s initial stamina is $k$. Without exceeding the stamina limit, Xiao Lan wants to find a placement method such that the sequence of gem magic values in these $n$ boxes has the maximum lexicographical order (note: an empty box is recorded as $-1$ in this sequence). As a follower of Xiao Lan, please help him find this placement method. **Explanation of lexicographical order**: In this problem, lexicographical order is compared by gem magic values. For two magic value sequences $a$ and $b$ of the same length $L$, if there exists a position $i$ such that $a_j = b_j$ holds for all $1 \le j < i$, but $a_i < b_i$, then sequence $a$ is lexicographically smaller than sequence $b$. Conversely, if $a_i > b_i$, then sequence $a$ is lexicographically larger than sequence $b$. If no such $i$ exists, then $a$ and $b$ are lexicographically equal.

The first line contains two integers $n$ and $k$, separated by one space, representing the number of gems and Xiao Lan’s initial stamina. The second line contains $n$ integers $a_1, a_2,\cdots , a_n$, separated by one space, representing the magical energy value of each gem.

Output one line containing $n$ integers, separated by one space, representing the magical energy value of the gem in each magic box. If a box is empty, output $-1$ at the corresponding position.

Before starting to place gems, the stamina is $3$, and the arrangement of gems in the boxes is $[-1, -1, -1]$. 1. Put the $2$-nd gem into the $1$-st box, obtaining $[3, -1, -1]$, with remaining stamina $2$. 2. Put the $3$-rd gem into the $2$-nd box, obtaining $[3, 2, -1]$, with remaining stamina $1$. Finally, the arrangement of gems in the boxes is $[3, 2, -1]$. Clearly, there is no better placement method than this. Constraints for $20\%$ of the testdata: $1 \le n \le 5 \times 10^3$, $0 \le k \le 3 \times 10^6$, $1 \le a_i \le 10^5$. Constraints for all testdata: $1 \le n \le 10^5$, $0 \le k \le 10^9$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5