P15652 [NOI Qualifier Joint Contest 2026] Permutation Game

**This is an interactive problem.** Submission notes: 1. Do not include the header file `perm.h`. 2. Paste the following at the top of your file: ```cpp #include void init(int, int); std::vector perm(int); int query(int, int); ``` 3. Submit using C++ 17 / 20.

Xiao H and Xiao L are playing a game of guessing a permutation. Xiao H has a permutation $p = [p_0, p_1, \dots, p_{n-1}]$ of $0 \sim n-1$. Now Xiao L knows the length $n$ of the permutation, and he wants to guess this permutation $p$ through a special kind of queries. Specifically, Xiao L can ask Xiao H queries of the following form: - Given non-negative integers $l, r$ satisfying $0 \le l \le r \le n-1$, find the **smallest non-negative integer that does not appear** in $p_l, \dots, p_r$. However, Xiao H and Xiao L found that even with infinitely many queries, sometimes it is still impossible to uniquely determine the permutation $p$. So they agree on the following: suppose Xiao H’s answer is $p$, and Xiao L’s guessed permutation is $q$. If for any $0 \le l \le r \le n-1$, the smallest non-negative integer missing from the interval $p_l, \dots, p_r$ is always equal to the smallest non-negative integer missing from the interval $q_l, \dots, q_r$, then Xiao L’s guess is considered correct. To make the game harder, Xiao H limits the number of queries Xiao L can make. You need to help Xiao L guess Xiao H’s permutation. ### Implementation Details Contestants do not need to, and should not, implement the `main` function. Contestants need to make sure the submitted program includes the header file `perm.h`, i.e., add the following at the beginning of the program: ```cpp #include "perm.h" ``` In the submitted source file `perm.cpp`, contestants need to implement the following two functions: ```cpp void init(int c, int t); ``` - $c, t$ denote the test point ID and the number of testdata groups, respectively. $c = 0$ means this test point is the sample. - For each test point, this function will be called by the interactive library **exactly once** when the program starts running. ```cpp std::vector perm(int n); ``` - $n$ is the length of the permutation. - This function should return a permutation of $0 \sim n-1$, representing Xiao L’s guess. - For each test point, this function will be called by the interactive library **exactly $t$ times**. Contestants can make one query by calling the following function: ```cpp int query(int l, int r); ``` - $l, r$ specify the query interval. Contestants must ensure $0 \le l \le r \le n-1$. - This function returns the smallest non-negative integer that does not appear in $p_l, \dots, p_r$. - Contestants must ensure that each time the interactive library calls `perm`, the number of calls to this function does not exceed $6 \times 10^5$. **Note: In all cases, the interactive library used in the final tests will take no more than $0.1$ seconds to run, and it uses a fixed amount of memory, which is no more than $64$ MiB.** ### How to Run the Tester `grader.cpp` in the problem directory is a reference implementation of the interactive library. The interactive library used in the final tests is different from this reference implementation, so your solution should not rely on the library implementation. You can compile an executable in the problem directory using the following command: ```bash g++ grader.cpp perm.cpp -o perm -std=gnu++14 -O2 -static ```

For the compiled executable: - The executable will read input from **standard input** in the following format: - The first line contains two non-negative integers $c, t$, which are the test point ID and the number of testdata groups. - Then follow $t$ testdata groups. For each testdata group: * The first line contains a positive integer $n$, the length of the permutation. * The second line contains $n$ non-negative integers $p_0, p_1, \dots, p_{n-1}$, which is Xiao H’s permutation.

- The executable will output to **standard output** in the following format: - For each testdata group: * The first line contains a string indicating the result. Specifically, - `Correct` means the contestant’s returned result is correct; - `Wrong answer` means the contestant’s returned result is incorrect; - `Invalid operation` means the contestant’s call to `query` is invalid. * If the result is `Correct`, then the second line contains a non-negative integer, which is the maximum number of calls to `query` among all testdata groups.

### Sample 1 Explanation This sample contains one testdata group. For the first testdata group, Xiao H’s permutation is $p = [4, 2, 3, 5, 0, 1]$. Here is one possible interaction process: - Call `query(0, 3)`, and the interactive library returns the smallest non-negative integer missing from $4, 2, 3, 5$, which is $0$. - Call `query(3, 4)`, and the interactive library returns the smallest non-negative integer missing from $5, 0$, which is $1$. - Call `query(1, 5)`, and the interactive library returns the smallest non-negative integer missing from $2, 3, 5, 0, 1$, which is $4$. - Call `query(3, 5)`, and the interactive library returns the smallest non-negative integer missing from $5, 0, 1$, which is $2$. - Return $q = [4, 2, 5, 3, 0, 1]$. It can be proven that the permutation $q$ is considered correct. ### Sample 2 See `perm/perm2.in` and `perm/perm2.ans` in the contestant directory. This sample satisfies the constraints of test points $4 \sim 8$. ### Notes on Provided Files In this problem directory: 1. `grader.cpp` is the provided reference implementation of the interactive library. 2. `perm.h` is the header file; contestants do not need to care about its specific contents. 3. `template_perm.cpp` is the provided sample code, which contestants can refer to and use to implement their own code. Contestants should back up all provided files. During final evaluation, only `perm.cpp` in this problem directory will be tested. Any changes to files other than this program will not affect the evaluation results. ### Constraints For all testdata: - $t = 10$. - $2 \le n \le 3 \times 10^4$. - For all $0 \le i \le n-1$, we have $0 \le p_i \le n-1$, and $p$ is a permutation of $0 \sim n-1$. ::cute-table{tuack} | Test Point ID | $n =$ | Special Property | |:-:|:-:|:-:| | $1 \sim 3$ | $10$ | None | | $4 \sim 8$ | $10^2$ | None | | $9, 10$ | $3 \times 10^4$ | A | | $11, 12$ | ^ | B | | $13, 14$ | ^ | C | | $15 \sim 20$ | ^ | None | - Special property A: $p_0 = 0$. - Special property B: There exists a non-negative integer $k \in [0, n-1]$ such that $p_0, \dots, p_k$ is monotonically decreasing, and $p_k, \dots, p_{n-1}$ is monotonically increasing. - Special property C: $p$ is generated **independently and uniformly at random** among all permutations of $0 \sim n-1$. ### Scoring Note: - Contestants must not obtain internal information from the interactive library by illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. - **The interactive library used in the final evaluation is different from the sample interactive library.** **This problem will first be subject to the same limits as traditional problems**, e.g., compilation errors will cause the whole problem to score $0$ points, runtime errors, time limit exceeded, memory limit exceeded, etc. will cause the corresponding test points to score $0$ points. Contestants may only access variables they define and variables provided by the interactive library; attempting to access other address spaces may cause compilation errors or runtime errors. Each time the `perm` function is called, if the returned permutation is not considered correct, or if the call to `query` is invalid, or if the number of calls to `query` exceeds $6 \times 10^5$, then the corresponding test point scores $0$ points. On top of the above conditions: - For test points $1 \sim 3$, the program gets full score if and only if, each time `perm` is called, the number of calls to `query` does not exceed $10^2$. - For test points $4 \sim 8$, let $m$ be the maximum number of queries per call to `perm`. The program will receive $5 \cdot f(m)$ points, where $f$ is computed as follows: ::cute-table{tuack} | $m$ | $f(m) =$ | |:-:|:-:| | $m \le 100$ | $1$ | | $100 < m \le 200$ | $1 - \dfrac{\sqrt{m - 100}}{50}$ | | $200 < m \le 4950$ | $0.8 - \dfrac{\sqrt{m - 200}}{170}$ | | $m > 4950$ | $0$ | - For test points $9 \sim 20$, let $m$ be the maximum number of queries per call to `perm`. The program will receive $5 \cdot g(m)$ points, where $g$ is computed as follows: ::cute-table{tuack} | $m$ | $g(m) =$ | |:-:|:-:| | $m \le 30000$ | $1$ | | $30000 < m \le 30015$ | $1 - \dfrac{7(m - 30000)}{5(5m - 149991)}$ | | $30015 < m \le 60000$ | $0.75 - \dfrac{\sqrt{m - 30015}}{700}$ | | $m > 60000$ | $0.5 - \dfrac{\sqrt{m - 60000}}{2500}$ | Translated by ChatGPT 5