Background

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:

   #include <vector>
   void init(int, int);
   std::vector<int> perm(int);
   int query(int, int);
   

3. Submit using C++ 17 / 20.

Problem Description

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:

#include "perm.h"

In the submitted source file perm.cpp, contestants need to implement the following two functions:

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.

std::vector<int> 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:

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:

g++ grader.cpp perm.cpp -o perm -std=gnu++14 -O2 -static

Input Format

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.

Output Format

• 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.

0 1
6
4 2 3 5 0 1

Correct.
4

Hint

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}

• 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