Background

This is an interactive problem.

The interactive library and the special judge (spj) are provided by

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.

Problem Description

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

Input Format

See “Interaction Protocol”.

Output Format

See “Interaction Protocol”.

5
3 1 4 2 0

Hint

Explanation for Sample 1

The interactive process in the sample:

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<X \le 2.5 \times 10^4$, you will get $\left\lfloor75 \times \dfrac{2.5 \times 10^4-X}{1.5 \times 10^4}\right\rfloor$ points.
  • If $X \le 10^4$, you will get $75$ points.

Note

Translated from JOI 2020 / 2021 Open Contest C Monster Game.

Translated by ChatGPT 5