P10628 [JOI Open 2024] 图书馆 3 / Library 3

由于洛谷评测系统的限制，实际提交时，不需要引入 $\texttt{library3.h}$。你需要在代码中添加： ```cpp void answer(std::vector); int query(std::vector); ``` 请使用 C++ 20 提交，不保证使用其他标准提交能够通过。

几百年的时光弹指一瞬，JOI 城已然是一片废墟。IOI 酱——一个探险家，正在探索图书馆的故址。由探索结果得知： - JOI 城的图书馆中有一个水平的书架，上面有 $N$ 个**位置**来放书，从左到右依次编号为 $0\sim N-1$。一个位置只能放一本书。 - 有 $N$ 本书放在书架上，编号为 $0\sim N-1$。 - 定义 $N$ 本书的一个**摆放**为一种将 $N$ 本书放在 $N$ 个位置上的方式。 - 存在 $N$ 本书的一个**正确摆放**，其中第 $B_i$（$0\le i\le N-1$）本书放在位置 $i$ 上，其中 $B_i$ 两两不同。 书的摆放总会改变，而这个图书馆是通过不断重复以下步骤来将书还原成正确摆放的： > **操作** 令 $x$ 是最左边的书，满足 $x$ 的位置与它在正确摆放中的位置不同。令 $y$ 为 $x$ 正确位置上的书，交换 $x,y$。 尽管 IOI 酱找到了许多旧书，她无法得知书的正确摆放。然而，她发现了一台旧机器，可以执行上面的操作。如果指定一个摆放并向机器发起询问，机器就会回答从当前摆放到正确摆放，需要重复执行多少次操作。IOI 酱想要利用这台机器，获得书的正确摆放。由于机器过于老旧，她最多只能询问 $5\, 000$ 次。 你需要写一个程序。给定书架的信息，通过最多 $5\,000$ 次询问，找出书的正确摆放。 【实现细节】 **这是一道交互题，你只需要提交一个文件（`library3.cpp`）。** 你需要在文件中引入 `library3.h`，并实现以下函数： - `void solve(int N)`\ 该函数在每个测试点中被调用恰好一次。 - 参数 $N$ 代表书的数量。 在 `library3.cpp` 中，你可以调用以下函数： - `int query(const std::vector a)`\ IOI 酱用这个函数向机器发起询问。 - 参数 `a` 为一个长度为 $N$ 的数组，即要询问的摆放。也就是说，在指定的摆放中，第 `a[i]` 本书（$0\le i\le N-1$）被放在位置 $i$。 - 返回值为一个整数，即从指定的摆放到正确摆放，需要重复执行多少次操作。 - 参数中，数组 `a` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[1]**。 - 参数中，数组 `a` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[2]**。 - 参数中，数组 `a` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[3]**。 - 该函数最多只能被调用 $5\,000$ 次。如果超出调用次数，你的程序将被判为 **Wrong Answer[4]**。 - `void answer(std::vector b)`\ 你的程序用这个函数回答正确摆放。 - 参数 `b` 为一个长度为 $N$ 的数组，即正确摆放。也就是说，在正确摆放中，第 `b[i]` 本书（$0\le i\le N-1$）被放在位置 $i$。 - 参数中，数组 `b` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[5]**。 - 参数中，数组 `b` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[6]**。 - 参数中，数组 `b` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[7]**。 - 如果你回答的摆放并不是正确摆放，你的程序将被判为 **Wrong Answer[8]**。 - 该函数必须被调用恰好一次。如果超出调用次数，你的程序将被判为 **Wrong Answer[9]**。如果未调用，你的程序将被判为 **Wrong Answer[10]**。 【注意事项】 你的程序可以定义其他函数，也可以使用全局变量。 你的程序不得使用标准输入输出流，不得以任何形式读写其他文件。但是，你的程序可以使用标准错误流来输出调试信息。 【编译运行】 可以从附件中获取 sample grader。Sample grader 即为文件 `grader.cpp`。将 `grader.cpp`，`library3.cpp`，`library3.h` 放置在同一目录下，运行以下命令即可编译你的程序。你也可以运行文件 `compile.sh` 来编译程序。 > 编译命令：`g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp` 编译成功的话，会生成可执行文件 `grader`。注意，实际评测时用的 grader 与 sample grader 是不同的。Sample grader 会以单进程方式执行，从标准输入流中读取数据，输出结果到标准输出流。 *赛时公告：Sample grader 是非适应性的。实际评测时使用的 grader 是否适应是未知的。

Sample grader 按照以下方式读取输入： > $N$\ > $B_0$ $B_1$ $\cdots$ $B_{N-1}$ 在正确摆放中，第 $B_i$（$0\le i\le N-1$）本书放在位置 $i$ 上。

Sample grader 会输出以下结果： - 如果你的程序被评为正确的，返回调用 `query` 函数的次数。例如：`Accepted: 3000`。 - 否则，如果你的程序满足任一形式的错误，则按照题目描述中的错误类型输出。例如：`Wrong Answer[3]`。 如果你的程序同时满足多种错误的条件，只会输出一种错误。

如下是一种可能的交互过程： | 调用 | 调用 | 返回值 | | :--: | :--:| :--: | | `solve(4)` | | | | | `query([0, 1, 2, 3])` | `3` | | | `query([1, 3, 0, 2])` | `2` | | | `query([3, 0, 1, 2])` | `2` | | | `query([2, 0, 3, 1])` | `0` | | | `answer([2, 0, 3, 1])` | | 考虑调用 `query([0, 1, 2, 3])`。操作将会按照如下方式进行： - 交换第 $0$ 本书和第 $1$ 本书的位置。于是，第 $1,0,2,3$ 本书分别被放在位置 $0,1,2,3$ 上。 - 交换第 $1$ 本书和第 $3$ 本书的位置。于是，第 $3,0,2,1$ 本书分别被放在位置 $0,1,2,3$ 上。 - 交换第 $3$ 本书和第 $2$ 本书的位置。于是，第 $2,0,3,1$ 本书分别被放在位置 $0,1,2,3$ 上。 在 $3$ 次操作后，将指定的摆放还原成了正确的摆放，所以返回值为 `3`。 样例满足所有子任务的限制条件。 ### 数据范围 - $2 \le N \le 500$； - $0 \le B_i \le N - 1$（$0 \le i \le N - 1$）； - $B_i\neq B_j$（$0 \le i < j \le N - 1$）； - 输入数字全为整数。 ### 子任务 1. （$2 $ points）$N \le 6$； 2. （$19$ points）$N \le 100$； 3. （$79$ points）无额外约束。 由 Starrykiller 根据英文题面翻译。