{"problem":{"name":"[JOI Open 2024] 图书馆 3 / Library 3","description":{"content":"几百年的时光弹指一瞬，JOI 城已然是一片废墟。IOI 酱——一个探险家，正在探索图书馆的故址。由探索结果得知： - JOI 城的图书馆中有一个水平的书架，上面有 $N$ 个**位置**来放书，从左到右依次编号为 $0\\sim N-1$。一个位置只能放一本书。 - 有 $N$ 本书放在书架上，编号为 $0\\sim N-1$。 - 定义 $N$ 本书的一个**摆放**为一种将 $N$ 本书放在 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10628"},"statements":[{"statement_type":"Markdown","content":"几百年的时光弹指一瞬，JOI 城已然是一片废墟。IOI 酱——一个探险家，正在探索图书馆的故址。由探索结果得知：\n\n- JOI 城的图书馆中有一个水平的书架，上面有 $N$ 个**位置**来放书，从左到右依次编号为 $0\\sim N-1$。一个位置只能放一本书。\n- 有 $N$ 本书放在书架上，编号为 $0\\sim N-1$。\n- 定义 $N$ 本书的一个**摆放**为一种将 $N$ 本书放在 $N$ 个位置上的方式。\n- 存在 $N$ 本书的一个**正确摆放**，其中第 $B_i$（$0\\le i\\le N-1$）本书放在位置 $i$ 上，其中 $B_i$ 两两不同。\n\n书的摆放总会改变，而这个图书馆是通过不断重复以下步骤来将书还原成正确摆放的：\n\n> **操作** 令 $x$ 是最左边的书，满足 $x$ 的位置与它在正确摆放中的位置不同。令 $y$ 为 $x$ 正确位置上的书，交换 $x,y$。\n\n尽管 IOI 酱找到了许多旧书，她无法得知书的正确摆放。然而，她发现了一台旧机器，可以执行上面的操作。如果指定一个摆放并向机器发起询问，机器就会回答从当前摆放到正确摆放，需要重复执行多少次操作。IOI 酱想要利用这台机器，获得书的正确摆放。由于机器过于老旧，她最多只能询问 $5\\, 000$ 次。\n\n你需要写一个程序。给定书架的信息，通过最多 $5\\,000$ 次询问，找出书的正确摆放。\n\n【实现细节】\n\n**这是一道交互题，你只需要提交一个文件（`library3.cpp`）。**\n\n你需要在文件中引入 `library3.h`，并实现以下函数：\n\n- `void solve(int N)`\\\n该函数在每个测试点中被调用恰好一次。\n    - 参数 $N$ 代表书的数量。\n\n在 `library3.cpp` 中，你可以调用以下函数：\n\n- `int query(const std::vector<int> a)`\\\nIOI 酱用这个函数向机器发起询问。\n    - 参数 `a` 为一个长度为 $N$ 的数组，即要询问的摆放。也就是说，在指定的摆放中，第 `a[i]` 本书（$0\\le i\\le N-1$）被放在位置 $i$。\n    - 返回值为一个整数，即从指定的摆放到正确摆放，需要重复执行多少次操作。\n    - 参数中，数组 `a` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[1]**。\n    - 参数中，数组 `a` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[2]**。\n    - 参数中，数组 `a` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[3]**。\n    - 该函数最多只能被调用 $5\\,000$ 次。如果超出调用次数，你的程序将被判为 **Wrong Answer[4]**。\n\n- `void answer(std::vector<int> b)`\\\n你的程序用这个函数回答正确摆放。\n    - 参数 `b` 为一个长度为 $N$ 的数组，即正确摆放。也就是说，在正确摆放中，第 `b[i]` 本书（$0\\le i\\le N-1$）被放在位置 $i$。\n    - 参数中，数组 `b` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[5]**。\n    - 参数中，数组 `b` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[6]**。\n    - 参数中，数组 `b` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[7]**。\n    - 如果你回答的摆放并不是正确摆放，你的程序将被判为 **Wrong Answer[8]**。\n    - 该函数必须被调用恰好一次。如果超出调用次数，你的程序将被判为 **Wrong Answer[9]**。如果未调用，你的程序将被判为 **Wrong Answer[10]**。\n\n【注意事项】\n\n你的程序可以定义其他函数，也可以使用全局变量。\n\n你的程序不得使用标准输入输出流，不得以任何形式读写其他文件。但是，你的程序可以使用标准错误流来输出调试信息。\n\n【编译运行】\n\n可以从附件中获取 sample grader。Sample grader 即为文件 `grader.cpp`。将 `grader.cpp`，`library3.cpp`，`library3.h` 放置在同一目录下，运行以下命令即可编译你的程序。你也可以运行文件 `compile.sh` 来编译程序。\n\n> 编译命令：`g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp`\n\n编译成功的话，会生成可执行文件 `grader`。注意，实际评测时用的 grader 与 sample grader 是不同的。Sample grader 会以单进程方式执行，从标准输入流中读取数据，输出结果到标准输出流。\n\n*赛时公告：Sample grader 是非适应性的。实际评测时使用的 grader 是否适应是未知的。\n\n## Input\n\nSample grader 按照以下方式读取输入：\n\n> $N$\\\n> $B_0$ $B_1$ $\\cdots$ $B_{N-1}$\n\n在正确摆放中，第 $B_i$（$0\\le i\\le N-1$）本书放在位置 $i$ 上。\n\n## Output\n\nSample grader 会输出以下结果：\n\n- 如果你的程序被评为正确的，返回调用 `query` 函数的次数。例如：`Accepted: 3000`。\n- 否则，如果你的程序满足任一形式的错误，则按照题目描述中的错误类型输出。例如：`Wrong Answer[3]`。\n\n如果你的程序同时满足多种错误的条件，只会输出一种错误。\n\n[samples]\n\n## Background\n\n由于洛谷评测系统的限制，实际提交时，不需要引入 $\\texttt{library3.h}$。你需要在代码中添加：\n\n```cpp\nvoid answer(std::vector<int>);\nint query(std::vector<int>);\n```\n\n请使用 C++ 20 提交，不保证使用其他标准提交能够通过。\n\n## Note\n\n如下是一种可能的交互过程：\n\n| 调用 | 调用 | 返回值 |\n| :--: | :--:| :--: |\n| `solve(4)` | | |\n| | `query([0, 1, 2, 3])` | `3` |\n| | `query([1, 3, 0, 2])` | `2` |\n| | `query([3, 0, 1, 2])` | `2` |\n| | `query([2, 0, 3, 1])` | `0` |\n| | `answer([2, 0, 3, 1])` | |\n\n考虑调用 `query([0, 1, 2, 3])`。操作将会按照如下方式进行：\n\n- 交换第 $0$ 本书和第 $1$ 本书的位置。于是，第 $1,0,2,3$ 本书分别被放在位置 $0,1,2,3$ 上。\n- 交换第 $1$ 本书和第 $3$ 本书的位置。于是，第 $3,0,2,1$ 本书分别被放在位置 $0,1,2,3$ 上。\n- 交换第 $3$ 本书和第 $2$ 本书的位置。于是，第 $2,0,3,1$ 本书分别被放在位置 $0,1,2,3$ 上。\n\n在 $3$ 次操作后，将指定的摆放还原成了正确的摆放，所以返回值为 `3`。\n\n样例满足所有子任务的限制条件。\n\n### 数据范围\n\n- $2 \\le N \\le 500$；\n- $0 \\le B_i \\le N - 1$（$0 \\le i \\le N - 1$）；\n- $B_i\\neq B_j$（$0 \\le i < j \\le N - 1$）；\n- 输入数字全为整数。\n\n### 子任务\n\n1. （$2 $ points）$N \\le 6$；\n2. （$19$ points）$N \\le 100$；\n3. （$79$ points）无额外约束。\n\n由 Starrykiller 根据英文题面翻译。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10628","tags":["二分","2024","交互题","Special Judge","置换","JOI（日本）"],"sample_group":[["4\n2 0 3 1",""]],"created_at":"2026-03-03 11:09:25"}}