#214493. [JOISC 2018] 图书馆 / Library

提交注意事项：

1. 不要引入头文件 library.h
2. 在文件头粘贴如下的内容:

#include <vector>
int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);

数百年后，JOI 城市已成废墟。探险家 IOI-chan 正在探索曾经建造图书馆的区域。根据勘探结果，已知以下信息：

• 图书馆的书架上共有 本书。这些书从左到右排成一列。
• 这 本书编号为 至 。但书架上书籍的排列顺序可能与书的编号顺序不同。
• 通过一次操作，可以一次性取走书架上连续放置的若干本书。

不幸的是，IOI-chan 未能在图书馆中找到旧书。但她发现了一台管理图书馆书架操作的机器。如果我们指定一个或多个书的编号并向机器发送查询，机器会返回仅取走这些书所需的最少操作次数。

IOI-chan 希望通过向机器发送查询来确定书架上书籍的排列顺序。然而，由于无论书籍顺序是正序还是倒序，机器返回的答案都相同，她无需指定书籍是从左到右还是从右到左排列。

由于机器年代久远，她最多只能向机器发送 20000 次查询。

任务

编写一个程序，通过向机器发送最多 20000 次查询，确定书架上书籍的排列顺序。无需指定书籍是从左到右还是从右到左排列。

实现细节

你需要实现以下函数。程序应包含函数定义 int Query(const std::vector<int>& M); 和 void Answer(const std::vector<int>& res);。程序不应当引入外部头文件。请使用不低于 C++17 的语言版本提交代码。

• void Solve(int N)

  对于每个测试用例，该函数将被调用一次。

  • 参数 表示书架上书籍的数量 。

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

• int Query(const std::vector<int>& M)

  • 如果指定了一个或多个书的编号，该函数返回仅取走这些书所需的最少操作次数。

  • 从书架上取走的书籍由参数 指定， 是一个大小为 的向量。对于每个 （），若 ，则表示不取走第 本书；若 ，则表示取走第 本书。若 的大小与 不同，你的程序将被视为 Wrong Answer [1]。对于每个 ， 的值应为 0 或 1。至少应存在一个 （）满足 。若以上两个条件中至少有一个未满足，你的程序将被视为 Wrong Answer [2]。若函数 Query 被调用超过 20000 次，你的程序将被视为 Wrong Answer [3]。

• void Answer(const std::vector<int>& res)

  • 使用此函数，你的程序应输出书架上书籍的排列顺序。无需指定书籍是从左到右还是从右到左排列。
  • 参数 是一个大小为 的向量，用于描述书架上书籍的排列顺序。对于每个 （），从左数第 本书的编号为 。若 的大小与 不同，你的程序将被视为 Wrong Answer [4]。 应为介于 1 和 之间的整数（含端点）。若此条件未满足，你的程序将被视为 Wrong Answer [5]。此外，整数 应互不相同。若此条件未满足，你的程序将被视为 Wrong Answer [6]。

当函数 Solve 结束时，若调用函数 Answer 的次数不等于 1，你的程序将被视为 Wrong Answer [7]。

若函数 Solve 所指定的书籍顺序与书架上实际的书籍顺序不同，你的程序将被视为 Wrong Answer [8]。无需指定书籍是从左到右还是从右到左排列。

重要提示

• 你的程序可以为内部使用实现其他函数，或使用全局变量。
• 你的程序不应使用标准输入和标准输出。你的程序不应以任何方式与其他文件通信。但你的程序可以向标准错误输出调试信息。

从标准输入读取以下数据：

• 第一行包含整数 ，表示书架上书籍的数量。
• 接下来的 行中，第 行（）包含整数 。这表示从左数第 本书的编号为 。

当程序成功终止时，样例评测器将以下信息写入标准输出。（引号实际不会输出。）

• 若你的程序被视为正确，样例评测器将以如下格式输出调用函数 Query 的次数：“Accepted : 100.”
• 若你的程序被视为 Wrong Answer，样例评测器将以如下格式输出其类型：“Wrong Answer [1].”

若你的程序被视为多种类型的 Wrong Answer，样例评测器仅报告其中一种。

样例输入 1

5
4
2
5
3
1

样例输出 1

样例 1 解释

调用 Query({1,1,1,0,0}) 得到 。再调用 Answer({4,2,5,3,1})。

在本题中，无需指定书籍是从左到右还是从右到左排列。因此，若你的程序调用 Answer({1,3,5,2,4})，且其参数顺序为逆序，仍被视为正确。

数据范围

所有输入数据满足以下条件。关于 和 的含义，请参见“样例评测器的输入”。

• 。
• （）。
• （）。

子任务

共有 2 个子任务。每个子任务的得分及额外约束如下：

子任务 1（19 分）

• 。

子任务 2（81 分）

无额外约束。

翻译由 Qwen3-235B 完成