P14375 [JOISC 2018] 图书馆 / Library

数百年后，JOI 城市已成废墟。探险家 IOI-chan 正在探索曾经建造图书馆的区域。根据勘探结果，已知以下信息： - 图书馆的书架上共有 $N$ 本书。这些书从左到右排成一列。 - 这 $N$ 本书编号为 $1$ 至 $N$。但书架上书籍的排列顺序可能与书的编号顺序不同。 - 通过一次操作，可以一次性取走书架上连续放置的若干本书。 不幸的是，IOI-chan 未能在图书馆中找到旧书。但她发现了一台管理图书馆书架操作的机器。如果我们指定一个或多个书的编号并向机器发送查询，机器会返回仅取走这些书所需的最少操作次数。 IOI-chan 希望通过向机器发送查询来确定书架上书籍的排列顺序。然而，由于无论书籍顺序是正序还是倒序，机器返回的答案都相同，她无需指定书籍是从左到右还是从右到左排列。 由于机器年代久远，她最多只能向机器发送 20000 次查询。 **任务** 编写一个程序，通过向机器发送最多 20000 次查询，确定书架上书籍的排列顺序。无需指定书籍是从左到右还是从右到左排列。 ### 实现细节 你需要实现以下函数。程序应包含函数定义 `int Query(const std::vector& M);` 和 `void Answer(const std::vector& res);`。程序不应当引入外部头文件。请使用不低于 C++17 的语言版本提交代码。 - `void Solve(int N)` 对于每个测试用例，该函数将被调用一次。 - 参数 $N$ 表示书架上书籍的数量 $N$。 你的程序可以调用以下函数。 - `int Query(const std::vector& M)` - 如果指定了一个或多个书的编号，该函数返回仅取走这些书所需的最少操作次数。 - 从书架上取走的书籍由参数 $M$ 指定，$M$ 是一个大小为 $N$ 的向量。对于每个 $i$（$1 \le i \le N$），若 $M[i-1] = 0$，则表示不取走第 $i$ 本书；若 $M[i-1] = 1$，则表示取走第 $i$ 本书。若 $M$ 的大小与 $N$ 不同，你的程序将被视为 **Wrong Answer [1]**。对于每个 $i$，$M[i-1]$ 的值应为 0 或 1。至少应存在一个 $i$（$1 \le i \le N$）满足 $M[i-1] = 1$。若以上两个条件中至少有一个未满足，你的程序将被视为 **Wrong Answer [2]**。若函数 `Query` 被调用超过 20000 次，你的程序将被视为 **Wrong Answer [3]**。 - `void Answer(const std::vector& res)` - 使用此函数，你的程序应输出书架上书籍的排列顺序。无需指定书籍是从左到右还是从右到左排列。 - 参数 $res$ 是一个大小为 $N$ 的向量，用于描述书架上书籍的排列顺序。对于每个 $i$（$1 \le i \le N$），从左数第 $i$ 本书的编号为 $res[i-1]$。若 $res$ 的大小与 $N$ 不同，你的程序将被视为 **Wrong Answer [4]**。$res[i-1]$ 应为介于 1 和 $N$ 之间的整数（含端点）。若此条件未满足，你的程序将被视为 **Wrong Answer [5]**。此外，整数 $res[0], res[1], \dots, res[N-1]$ 应互不相同。若此条件未满足，你的程序将被视为 **Wrong Answer [6]**。 当函数 `Solve` 结束时，若调用函数 `Answer` 的次数不等于 1，你的程序将被视为 **Wrong Answer [7]**。 若函数 `Solve` 所指定的书籍顺序与书架上实际的书籍顺序不同，你的程序将被视为 **Wrong Answer [8]**。无需指定书籍是从左到右还是从右到左排列。 **重要提示** - 你的程序可以为内部使用实现其他函数，或使用全局变量。 - 你的程序不应使用标准输入和标准输出。你的程序不应以任何方式与其他文件通信。但你的程序可以向标准错误输出调试信息。

从标准输入读取以下数据： - 第一行包含整数 $N$，表示书架上书籍的数量。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含整数 $A_i$。这表示从左数第 $i$ 本书的编号为 $A_i$。

当程序成功终止时，样例评测器将以下信息写入标准输出。（引号实际不会输出。） - 若你的程序被视为正确，样例评测器将以如下格式输出调用函数 `Query` 的次数：“Accepted : 100.” - 若你的程序被视为 **Wrong Answer**，样例评测器将以如下格式输出其类型：“Wrong Answer [1].” 若你的程序被视为多种类型的 **Wrong Answer**，样例评测器仅报告其中一种。

### 样例 1 解释 调用 `Query({1,1,1,0,0})` 得到 $2$。再调用 `Answer({4,2,5,3,1})`。 在本题中，无需指定书籍是从左到右还是从右到左排列。因此，若你的程序调用 `Answer({1,3,5,2,4})`，且其参数顺序为逆序，仍被视为正确。 ### 数据范围 所有输入数据满足以下条件。关于 $N$ 和 $A_i$ 的含义，请参见“样例评测器的输入”。 - $1 \le N \le 1000$。 - $1 \le A_i \le N$（$1 \le i \le N$）。 - $A_i \ne A_j$（$1 \le i < j \le N$）。 ### 子任务 共有 2 个子任务。每个子任务的得分及额外约束如下： **子任务 1（19 分）** - $N \le 200$。 **子任务 2（81 分）** 无额外约束。 翻译由 Qwen3-235B 完成