Bajtosz 进入了电视节目“Jeden z n!”的决赛。在这个节目中，选手需要猜出一个隐藏的排列 $p$，该排列包含数字 $0, 1, 2, \dots, n - 1$。在每一轮中，选手通过选择一个排列 $q$（包含数字 $0, 1, 2, \dots, n - 1$）以及两个数字 $a, b \in \{0, 1, \dots, n - 1\}$ 来提出问题。主持人首先确定排列 $r$，它是排列 $q$ 对排列 $p$ 的复合。因此，对于每个 $i \in \{0, 1, \dots, n - 1\}$，在排列 $r$ 中，数字 $i$ 映射到数字 $q(p(i))$。随后，主持人会告知选手数字 $a$ 和 $b$ 是否在排列 $r$ 的同一个循环中。形式上，排列 $r$ 中包含 $a$ 的循环是序列 $a, r(a), r(r(a)), r(r(r(a))), \dots$（当数字 $a$ 第二次出现时，我们可以结束该序列）。我们询问的是数字 $b$ 是否出现在这样的序列中。
例如，考虑排列 $p = [3, 2, 1, 0, 4]$。这个记号表示在排列 $p$ 中，数字 $0$ 映射到 $3$，数字 $1$ 映射到 $2$，数字 $2$ 映射到 $1$，数字 $3$ 映射到 $0$，数字 $4$ 映射到 $4$。对其应用排列 $q = [2, 0, 4, 3, 1]$，我们得到排列 $r = [3, 4, 0, 2, 1]$，如下图所示。
所得排列 $r$ 的循环如下图所示：
例如，数字 $2$ 和 $3$ 在排列 $r$ 中位于同一个循环中，而数字 $2$ 和 $4$ 则不在。
选手的目标是在有限的询问次数内猜出排列 $p$。请帮助 Bajtosz 制定策略，以在电视节目中获得尽可能高的奖金。
交互
这是一个交互式任务。你需要编写一个程序，使用提供的库来参与电视节目。要使用该库，请在你的程序中包含：
- C++:
#include "perlib.h" - Python:
from perlib import *
你的程序将通过以下命令进行编译/运行：
- C++:
g++ -O3 -static per.cpp perlib.cpp -std=c++20 - Python:
python3 per.py
以下函数返回排列的长度 $n$ ($1 \le n \le 500$)：
- C++:
int daj_n() - Python:
daj_n() -> int
下一个函数返回最大询问次数 $z$。如果你的程序询问次数超过此限制，将获得“错误答案”判决。
- C++:
int daj_z() - Python:
daj_z() -> int
以下函数返回子任务编号（参见“评分”部分）。对于样例测试，其返回值为 $1$。
- C++:
int daj_podzadanie() - Python:
daj_podzadanie() -> int
你可以使用以下函数来了解 $a$ 和 $b$ 是否在排列 $r$（即排列 $q$ 对（你未知的）排列 $p$ 的复合）的同一个循环中。如果 $a$ 和 $b$ 在同一个循环中，函数返回 true（Python 中为 True），否则返回 false（Python 中为 False）。
- C++:
bool zapytaj(std::vector<int> q, int a, int b) - Python:
zapytaj(q: list[int], a: int, b: int) -> bool
最后一个函数用于提交排列 $p$ 作为答案。
- C++:
void odpowiedz(std::vector<int> p) - Python:
odpowiedz(p: list[int]) -> None
在 C++ 中，该函数会终止程序。而在 Python 中，该函数不会终止程序。用户应在调用此函数后立即自行终止程序。
函数中排列的表示方式如下：
- C++: 排列 $q$ 和 $p$ 作为长度为 $n$ 的向量 (
std::vector) 传递给函数。位置 $i$ ($0 \le i < n$) 处的数字应等于 $i$ 在所描述排列中映射到的数字。 - Python: 排列 $q$ 和 $p$ 作为长度为 $n$ 的
int类型列表传递。位置 $i$ ($0 \le i < n$) 处的数字应等于 $i$ 在所描述排列中映射到的数字。不要传递生成器或numpy数组。生成器可以通过list(变量名)指令转换为列表。
你的程序不得打开任何文件或使用标准输入输出。可以使用标准诊断输出 (stderr)，但请记住这会消耗宝贵的时间。
样例
排列 $p = [3, 2, 1, 0, 4]$，以及问题部分中出现的排列 $q = [2, 0, 4, 3, 1]$ 和 $r = [3, 4, 0, 2, 1]$ 已在第一页的图中展示。
例如，代表排列 $[3, 2, 1, 0, 4]$ 的 std::vector 对象写作 {3,2,1,0,4}。
| 调用函数 | 返回值 | 说明 |
|---|---|---|
daj_n() |
$5$ | $n = 5$，隐藏排列 $p$ 为 $[3, 2, 1, 0, 4]$ |
zapytaj({0,1,2,3,4}, 0, 1) |
false |
$0$ 和 $1$ 不在同一个循环中 |
zapytaj({0,1,2,3,4}, 1, 2) |
true |
$1$ 和 $2$ 在同一个循环中 |
zapytaj({0,1,2,3,4}, 2, 3) |
false |
$2$ 和 $3$ 不在同一个循环中 |
zapytaj({0,1,2,3,4}, 0, 3) |
true |
$0$ 和 $3$ 在同一个循环中 |
zapytaj({2,0,4,3,1}, 4, 1) |
true |
在排列 $r = [3, 4, 0, 2, 1]$ 中，$4$ 和 $1$ 在同一个循环中 |
zapytaj({2,0,4,3,1}, 4, 0) |
false |
在排列 $r = [3, 4, 0, 2, 1]$ 中，$4$ 和 $0$ 不在同一个循环中 |
zapytaj({2,0,4,3,1}, 2, 4) |
false |
在排列 $r = [3, 4, 0, 2, 1]$ 中，$2$ 和 $4$ 不在同一个循环中 |
zapytaj({2,0,4,3,1}, 4, 3) |
false |
在排列 $r = [3, 4, 0, 2, 1]$ 中，$4$ 和 $3$ 不在同一个循环中 |
zapytaj({2,0,4,3,1}, 0, 3) |
true |
在排列 $r = [3, 4, 0, 2, 1]$ 中，$0$ 和 $3$ 在同一个循环中 |
odpowiedz({3,2,1,0,4}) |
— | 只有该排列符合上述所有回答 |
子任务
测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试组组成。
| 子任务 | 数据范围 | 分数 |
|---|---|---|
| $1$ | $n \le 6, z = 100\,000$ | $10$ |
| $2$ | $n \le 30, z = 100\,000$ | $20$ |
| $3$ | $n \le 100, z = 15\,000$ | $20$ |
| $4$ | $n \le 500, z = 15\,000$ | $10$ |
| $5$ | $n \le 500, z = 7000, p$ 为单个循环 | $10$ |
| $6$ | $n \le 500, z = 7000$ | $20$ |
| $7$ | $n \le 500, z = 5000$ | $10$ |
库在最开始确定排列 $p$，然后回答后续问题。
实现细节
在 SIO 的“文件与测试”部分，你可以找到库的示例实现以及该库所接受格式的样例测试。
示例库在输入的第一行依次读取 $n$ 和 $z$，在第二行读取 $n$ 个数字，表示排列 $p$ 的连续值：$p(0), p(1), \dots, p(n - 1)$。函数 daj_podzadanie() 返回 $-1$。
用于评估你解决方案的库实现可能与示例不同。
注意：在此任务中，SIO 上不提供试运行，也不提供计算机上的评分脚本。