P8126 [BalticOI 2021] The Collection Game (Day2)

**本题是交互题。** 你的代码不需要也不应该包含 `swaps.h` 头文件，但应包含以下声明： ```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 } ```

您要参观博物馆的 $N$ 个展馆，因为您之前有入狱史（BalticOI 2021 Day2 A），所以博物馆官方仅允许您参观小于等于 $V$ 次。每一次参观您可以浏览多次，每一次浏览您可以浏览 **一对** 展馆 $(i,j)$，然后您就可以得知这两个展馆哪个展馆的艺术价值最高。为了不浪费您的时间，每一次参观每个展馆只能浏览最多一次。 不幸的是，因为您的入狱史，博物馆 **可能** 会交换您要浏览的一对展馆里的展品，这样您得到的艺术价值关系就是反过来的，您最后对这 $N$ 个展馆中的其中一个的排名也应基于 **最后一次** 对这个展馆的浏览。 现在请通过浏览来确定这 $N$ 个展馆的艺术价值的排列。 ### 交互格式 您需要实现函数 `void solve (int N, int V)`，其中 $N $ 和 $V$ 为展馆数量和最多参观次数。 `solve` 函数只被调用一次，并且可以在 `solve` 函数里面调用： - `void schedule (int i, int j)` 浏览一对展馆 $(i,j)$，博物馆有可能交换展品。 - `vector visit ()` 整理浏览结果，返回的序列按照浏览的展馆对数 $(i,j)$ 顺序返回若干个 $k$，如果第 $i$ 个展馆的艺术价值高于第 $j$ 个展馆，$k=1$，否则 $k=0$。 - `void answer (vector r)` $r$ 是一个长度为 $N$ 的序列，并且是一个 $1 \sim N$ 的排列，$r_i=p$ 代表第 $i$ 个展馆在这 $N$ 个展馆的艺术价值排序中排第 $p$ 个。 如果您函数的调用不满足要求，一次参观一个展馆浏览了超过 $1$ 次，或者参观了超过 $V$ 次，您的程序都会立即停止然后判为 `Not correct`。请不要在标准输出中输出任何东西，否则会被判为 `Security violation!`。 如果您使用 C++ 编码，请调用 swaps.h 头文件，如果您想检验您的程序的正确性，可以在下方附件中下载 sample_grader.cpp 与 swaps_sample.cpp，分别为您提供检验正确性和示例说明的作用。 如果您使用 Python 编码，可以在下方附件中下载 swaps_sample.py 检验。 交互库希望标准输入里有一行： - 一行两个整数 $N,V$。 随后，交互库会调用您的程序，最后，交互库会在标准输出中返回信息： |信息|意义| |:-:|:-:| |**Invalid input.**|标准输入的格式错误| |**Invalid schedule.**|`schedule` 函数调用无效| |**Out of visits.**|`visit` 函数调用超过 $V$ 次| |**Invalid answer.**|`answer` 函数调用无效| |**Wrong answer.**|`answer` 函数调用的 $r$ 错误| |**No answer.**|`solve` 函数没有调用 `answer` 函数| |**Correct: v visit(s) used.**|上述事件都没有发生，调用了 $V$ 次 `visit` 函数| 针对上面若干个错误的情况，交互库仅会返回 **Not correct**，或者正确的时候返回 **Correct**。每当出现上面的若干个错误，或者您的程序调用了 `answer` 函数时，程序会被自动停止。

见「交互格式」。

见「交互格式」。

#### 样例 1 解释 $N=4$，$V=50$，下面是一种合法的调用： |你的程序|返回值|博物馆是否交换 |:-:|:-:|:-:| |`schedule(1,2)`|-|否| |`schedule(3,4)`|-|是| |`visit()`|`{1,0}`|-| |`schedule(2,4)`|-|否| |`visit()`|`{1}`|-| |`answer({1,2,4,3})`|-|-| 对于上表，$r=\{2,1,4,3\}$ 也满足要求。如果第三次 `visit` 交换了，那么 $r=\{4,1,2,3\}$ 满足要求。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$V=5000$，博物馆永远不会交换展品。 - Subtask 2（10 pts）：$V \ge 1000$，博物馆永远不会交换展品。 - 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$。 对于 $100\%$ 的数据，$1 \le N \le 500$，$50 \le V \le 5000$。 #### 说明 翻译自 [BalticOI 2021 Day2 B The Collection Game](https://boi.cses.fi/files/boi2021_day2.pdf)。