4165. 「JOI Open 2024」图书馆 3

题目描述

译自 JOI Open 2024 T3 「図書館 3 / Library 3」。

经过数百年的时间，JOI 市已经变成了废墟。探险家 IOI 酱正在调查图书馆所在的地区。通过调查，他发现了以下事情。

JOI 市的图书馆有一个水平的书架，被隔板分成了 $N$ 个位置。位置从左边开始按顺序编号为 $0$ 到 $N-1$，每个位置只能放一本书。

书架上有 $N$ 本书。书上编号为 $0$ 到 $N-1$。

书的排列方式是指把 $N$ 本书全部放在 $N$ 个位置上的方法，每个位置只放一本书。

书有一种正确的排列方式，在正确的排列方式下，位置 $i$（$0 \leq i \leq N-1$）上放的书是书 $B_i$。而且 $B_i$ 互不相同。

书架上的书的顺序经常会变。这个图书馆在 $N$ 本书都放在书架上的时候，是通过重复以下的操作，来把书恢复到正确的排列方式：

1. 令在正确的排列方式和放置的位置不同的书中最左边的书是书 $x$。
2. 在正确的排列方式下，书 $x$ 要放的位置上，现在的排列方式放的书是书 $y$。
3. 把书 $x$ 和书 $y$ 的位置互换。

IOI 酱虽然找到了以前的藏书，但是很遗憾，他不知道正确的排列方式。不过，他发现了图书馆的书架管理机器。向这个机器询问一次，就可以求出从指定 $N$ 本书的排列方式开始，把所有的书恢复到正确的排列方式需要做几次操作。IOI 酱想要通过向这个机器询问几次，确定书的正确的排列方式，因为这台机器已经年久失修，所以询问的次数不能超过 $5000$ 次。

给定书架的信息，实现一个程序用不超过 $5000$ 次的询问，确定书的正确的排列方式。

实现细节

你需要在程序一开始使用预处理指令 #include 引入库 library3.h。它应当实现如下函数。

void solve(int N)

这个函数在每组测试数据中仅被调用一次。

• 参数 N 表示藏书的册数 $N$。

你的程序可以调用以下的函数。

int query(const std::vector<int> a)

使用这个函数，你的程序可以做一次查询。

• 参数 a 是长度为 $N$ 的数组，表示询问时指定的书的排列方式。具体地说，位置 $i$（$0 \leq i \leq N-1$）上放的书是 a[i]。
• 返回值是从指定的排列方式开始，把所有的书恢复到正确的排列方式需要做几次操作。
• 参数 a 的长度必须是 $N$。如果不满足这个条件，你的程序会被判为 Wrong Answer [1]。
• 参数 a 的每个元素必须在 $0 \sim N-1$ 之间。如果不满足这个条件，你的程序会被判为 Wrong Answer [2]。
• 参数 a 的每个元素必须互不相同。如果不满足这个条件，你的程序会被判为 Wrong Answer [3]。
• 函数 query 不能超过 $5000$ 次调用。如果超过 $5000$ 次调用，你的程序会被判为 Wrong Answer [4]。

void answer(std::vector<int> b)

这个函数用来回答书的正确的排列方式。

• 参数 b 是长度为 $N$ 的数组，表示回答时指定的书的排列方式。具体地说，位置 $i$（$0 \leq i \leq N-1$）上放的书是 b[i]。
• 参数 b 的长度必须是 $N$。如果不满足这个条件，你的程序会被判为 Wrong Answer [5]。
• 参数 b 的每个元素必须在 $0 \sim N-1$ 之间。如果不满足这个条件，你的程序会被判为 Wrong Answer [6]。
• 参数 b 的每个元素必须都互不相同。如果不满足这个条件，你的程序会被判为 Wrong Answer [7]。
• 指定的排列方式必须是正确的排列方式。如果不满足这个条件，你的程序会被判为 Wrong Answer [8]。
• 函数 answer 必须正好调用一次。如果函数 answer 调用了两次以上，你的程序会被判为 Wrong Answer [9]。如果函数 solve 的执行结束时，函数 answer 都没有被调用过，你的程序会被判为 Wrong Answer [10]。

注意事项

• 你的程序可以实现其它函数供内部使用，或者使用全局变量。
• 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而，你的程序可以将调试信息输出到标准错误输出。

编译和测试运行

你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。

样例交互器是文件 grader.cpp。为了测试你的程序，你需要将 grader.cpp，library3.cpp 和 library3.h 三个文件放在同一文件夹下，并且执行如下命令编译你的程序。你也可以运行 compile.sh 来编译你的程序。

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

当编译成功时，会生成一个可执行文件 grader。

请注意，实际的交互器和样例不同。样例交互器会作为单进程运行，即它会从标准输入中读取输入数据，并输出结果到标准输出。

样例交互器输入

样例交互器会从标准输入读取以下内容。

第一行一个整数 $N$。

第二行包含 $N$ 个整数 $B_0, B_1, \cdots, B_{N-1}$。其中 $B_i$（$0 \leq i \leq N-1$）是在正确的排列方式下，位置 $i$ 上放的书的编号。

样例交互器输出

样例交互器会输出如下内容到标准输出。

• 如果你的程序被判为正确，它会输出函数 query 的调用次数，如 Accepted: 22。然而，如果你的程序没有调用 query 函数并被判为正确，它会输出 Accepted: 0。
• 如果你的程序被判为任一类的答案错误，样例交互器会输出其类别，如 Wrong Answer [4]。

执行的程序如果满足了多个不正确答案的条件，显示的不正确答案的种类只有其中的一个。

样例交互

输入：

4
2 0 3 1

调用过程：

调用	返回值
solve(4)
query([0, 1, 2, 3])	3
query([1, 3, 0, 2])	2
query([3, 0, 1, 2])
query([2, 0, 3, 1])	0
answer([2, 0, 3, 1])

例如，query([0, 1, 2, 3]) 的调用是指定位置 $0,1,2,3$ 上分别放着书 $0,1,2,3$ 的排列方式，操作将按如下进行：

1. 把书 $0$ 和书 $1$ 的位置互换。此时位置 $0,1,2,3$ 上分别放着书 $1,0,2,3$。
2. 把书 $1$ 和书 $3$ 的位置互换。此时位置 $0,1,2,3$ 上分别放着书 $3,0,2,1$。
3. 把书 $3$ 和书 $2$ 的位置互换。此时位置 $0,1,2,3$ 上分别放着书 $2,0,3,1$。

把所有的书恢复到正确的排列方式需要做 $3$ 次操作，所以返回值是 $3$。

这组样例满足所有的子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 500$
• $0 \leq B_i \leq N-1$（$0 \leq i \leq N-1$）
• $B_i \neq B_j$（$0 \leq i < j \leq N-1$）
• 输入的值都是整数

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$N \leq 6$	2
2	$N \leq 100$	19
3	无附加限制	79