P7805 [JOI Open 2021] Monster Game / Monster Game

**This is an interactive problem.** The interactive library and the special judge (spj) are provided by @[Liking_Cpp_In_Luogu](https://www.luogu.com.cn/user/705620). Thanks for his contribution. Please do not include the header file `monster.h` in your code. Add `extern "C"` before the `Solve` function, and add `extern "C" bool Query(int,int);` at the beginning.

You have raised $N$ bookworms. They are numbered from $0$ to $N-1$. The strength of the $i$-th bookworm is $S_i$, where $S_i \in [0,N-1]$, and no two bookworms have the same strength. You may perform at most $25000$ “fight events”: - Choose two different bookworms $a,b$: - If $|S_a-S_b|=1$, the bookworm with the smaller strength wins. - If $|S_a-S_b|>1$, the bookworm with the larger strength wins. You should minimize the number of “fight events”. You can obtain the result of each “fight event”. Find the strengths of all bookworms. #### Interaction Protocol Your program must implement the following function: - `std::vector Solve(int N)` - For each test case, this function will be called exactly once. - $N$: the number of bookworms. - This function should return the array $T$ of strengths of these $N$ bookworms. - It must satisfy $|T|=N$, otherwise your program will be judged as `Wrong Answer [1]`. - It must satisfy $T_i\in [0,N-1]$, otherwise your program will be judged as `Wrong Answer [2]`. - It must satisfy $T_i=S_i$, otherwise your program will be judged as `Wrong Answer [3]`. Your program may call the following function: - `bool Query(int a, int b)` - You can use this function to perform a “fight event”. - $a,b$: bookworm $a$ fights bookworm $b$. - If $a$ wins, return `true`; otherwise return `false`. - It must satisfy $a \in [0,N-1]\land b \in [0,N-1]$, otherwise your program will be judged as `Wrong Answer [4]`. - It must satisfy $a \ne b$, otherwise your program will be judged as `Wrong Answer [5]`. - The number of calls to `Query` must not exceed $25000$. Otherwise your program will be judged as `Wrong Answer [6]`. **Special Notes** 1. Your program may call other functions in the standard library, or use global variables. 2. Your program must not use standard input or standard output.

See “Interaction Protocol”.

See “Interaction Protocol”.

#### Explanation for Sample 1 The interactive process in the sample: |Call|Return|Call|Return| |:-:|:-:|:-:|:-:| |`Solve(5)`|||| |||`Query(1, 0)`|`false`| |||`Query(4, 0)`|`false`| |||`Query(1, 3)`|`true`| ||`[3, 1, 4, 2, 0]`|| #### Sample Grader Program (Sample) The sample grader program reads the input in the following format: First line: $N$ Second line: $S_0\ S_1\ \cdots\ S_{N-1}$ The sample grader program reads the output in the following format: After your program terminates successfully, the sample interactor will output the following on standard output: - If your program is judged correct, the sample interactor will output something like `Accepted: 100`, where $100$ is the number of times your program called the `Query` function. - If your program is judged wrong, the output content is described in “Interaction Protocol”. If your program has multiple errors, the sample interactor will only judge one of them. Note that the interactor is adaptive for some testdata. That is, at the beginning the interactor does not have a fixed answer, and it will gradually respond according to previous calls to the `Query` function. It is guaranteed that there exists at least one set of answers consistent with the responses made by the interactive library. (The original problem had a tool to test this, but the checking file cannot be found now, so it is omitted.) #### Constraints and Notes **This problem uses bundled tests.** - Subtask 1 (10 pts): $N \le 200$. - Subtask 2 (15 pts): the actually used interactive library is not adaptive. - Subtask 3 (75 pts): no special restrictions. For $100\%$ of the data: - $4 \le N \le 1000$. - $0 \le S_i \le N-1$. - $S_i$ are guaranteed to be pairwise distinct. For Subtask 3, there is an additional scoring rule: If your program passes all testdata, then: - Let $X$ be the maximum number of calls to the `Query` function among all test cases in Subtask 3. - Your score will be computed as follows: - If $10^4