P10159 [DTCPC 2024] The last permutation

**The background of this problem is not entirely fictional and does not imply anything about any real person.**. Xiao L was the “white moonlight” (baiyueguang) of Xiao L in middle school. One day, Xiao L said on Moments that they wanted to play “Nong”, and Xiao L quickly studied how to download Honor of Kings. The next day, Xiao L said on Moments that they wanted to play PUBG, and Xiao L quickly studied how to download PUBG. But Xiao L soon broke up with Xiao L. Xiao L’s last feelings turned into a permutation. Unfortunately, Xiao L was not willing to tell everyone. However, after your constant questioning, Xiao L finally agreed to answer a few questions about the permutation.

There is a hidden permutation $p$ of length $n$. You may perform the following queries any number of times: choose a triple $(l, r, k)$ satisfying $1 \le l \le r \le n$, $1 \le k \le r - l + 1$. The interactive judge will return the $k$-th largest value among indices in $[l, r]$. For one query, the cost is $\frac{1}{r - l + 1}$. You need to determine the permutation within a total cost not exceeding $11.8$. The interactive judge is non-adaptive. That is, the permutation you need to find is already fixed before the interaction starts.

The first line contains a positive integer $t$ ($1 \le t \le 5$), the number of test cases. For each test case, one line contains $n$ ($1 \le n \le 1000$), the length of the permutation $p$. When you have determined the permutation, you should output in the form `! p1 p2 ... pn` to indicate the permutation you found. This problem uses IO interactive mode. ### Interaction Format - `? l r k`: query the $k$-th largest value among indices in $[l, r]$. - `! p1 p2 p3 ... pn`: output the answer. Please note: in each test case, ensure that the total cost of all queries does not exceed $11.8$. Also note that after each operation, you need to call the following function to flush the output buffer: - For C/C++: `fflush(stdout);` - For C++: `std::cout

See “Interaction Format”.

Translated by ChatGPT 5