Description

You want to visit $N$ exhibition halls in a museum. Because you have a criminal record (BalticOI 2021 Day2 A), the museum only allows you to make at most $V$ visits. In each visit, you can perform multiple comparisons. Each comparison lets you compare a pair of halls $(i, j)$, and then you will know which of the two halls has the higher artistic value. To avoid wasting your time, in each visit, each hall can be compared at most once.

Unfortunately, because of your criminal record, the museum may swap the exhibits in the pair of halls you compare, so the artistic value relation you obtain will be reversed. In the end, your ranking for each of the $N$ halls should be based on the last comparison involving that hall.

Now, determine the permutation of artistic values of these $N$ halls through comparisons.

Interaction

You need to implement the function void solve(int N, int V), where $N$ is the number of halls and $V$ is the maximum number of visits.

The function solve is called only once, and inside solve you may call:

• void schedule(int i, int j) Compare the pair of halls $(i, j)$. The museum may swap the exhibits.
• vector<int> visit() Finalize the comparisons of the current visit. It returns a sequence of results in the same order as the scheduled pairs $(i, j)$. For each pair, if hall $i$ has higher artistic value than hall $j$, then $k = 1$, otherwise $k = 0$.
• void answer(vector<int> r) Here $r$ is a sequence of length $N$, and it is a permutation of $1 \sim N$. $r_i = p$ means hall $i$ ranks $p$-th in artistic value among the $N$ halls.

If your function calls do not satisfy the requirements (for example, in a single visit you compare the same hall more than $1$ time, or you make more than $V$ visits), your program will be stopped immediately and judged as Not correct. Do not print anything to standard output, otherwise you will be judged as Security violation!.

If you use C++, include the swaps.h header file. If you want to test your program, you can download sample_grader.cpp and swaps_sample.cpp from the attachments below, which are used for correctness checking and as a sample explanation.

If you use Python, you can download swaps_sample.py from the attachments below for testing.

The interactive library expects one line in standard input:

• One line with two integers $N, V$.

Then the interactive library will call your program. Finally, the interactive library will print information to standard output:

For the error cases above, the interactive library will only output Not correct, or Correct when it is correct. Whenever any of the above errors occurs, or when your program calls answer, the program will be terminated automatically.

Input Format

See “Interaction”.

Output Format

See “Interaction”.

4 50

Hint

Sample 1 Explanation

$N = 4$, $V = 50$. The following is one valid sequence of calls:

For the table above, $r = \{2,1,4,3\}$ also satisfies the requirements. If the third visit swaps, then $r = \{4,1,2,3\}$ satisfies the requirements.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $V = 5000$, the museum never swaps exhibits.
• Subtask 2 (10 pts): $V \ge 1000$, the museum never swaps exhibits.
• Subtask 3 (5 pts): $N \le 100$, $V = 5000$.
• Subtask 4 (15 pts): $V = 5000$.
• Subtask 5 (15 pts): $V \ge 500$.
• Subtask 6 (35 pts): $V \ge 100$.
• Subtask 7 (15 pts): $V \ge 50$.

For $100\%$ of the testdata, $1 \le N \le 500$, $50 \le V \le 5000$.

Notes

Translated from BalticOI 2021 Day2 B The Collection Game。

Translated by ChatGPT 5