P8126 [BalticOI 2021] The Collection Game (Day2)

**This is an interactive problem.** Your code does not need and should not include the `swaps.h` header file, but it should include the following declarations: ```cpp extern "C" void schedule(int i, int j); extern "C" std::vector visit(); extern "C" void answer(std::vector r); extern "C" void solve(int N, int Q) { // Code Here } ```

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 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 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: |Message|Meaning| |:-:|:-:| |**Invalid input.**|Invalid standard input format| |**Invalid schedule.**|Invalid call to `schedule`| |**Out of visits.**|`visit` is called more than $V$ times| |**Invalid answer.**|Invalid call to `answer`| |**Wrong answer.**|The permutation $r$ passed to `answer` is incorrect| |**No answer.**|`solve` did not call `answer`| |**Correct: v visit(s) used.**|None of the above happened, and `visit` was called $V$ times| 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.

See “Interaction”.

See “Interaction”.

#### Sample 1 Explanation $N = 4$, $V = 50$. The following is one valid sequence of calls: |Your program|Return value|Does the museum swap| |:-:|:-:|:-:| |`schedule(1,2)`|-|No| |`schedule(3,4)`|-|Yes| |`visit()`|`{1,0}`|-| |`schedule(2,4)`|-|No| |`visit()`|`{1}`|-| |`answer({1,2,4,3})`|-|-| 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](https://boi.cses.fi/files/boi2021_day2.pdf)。 Translated by ChatGPT 5