interactive - المسألة

你最近学习了配交互库。

给定一条长度为 $n-1$ 的链，结点的标号为一个 $[1, n]$ 的排列。

每次，你可以查询这 $n$ 个点上的一条长为 $n-1$ 的链，交互库会返回这两条链公共的无向边数。

试在不超过 $3 \times 10^5$ 次查询内确定这条链。进一步地，你的得分和你所使用的查询次数有关。

注意：交互库不是自适应的，换言之，链在交互开始前就是确定的。

你必须引用 interactive.h 头文件。

你不需要、也不应该实现主函数。

你只需实现以下函数：

std::vector<int> solve(int n);

该函数会被调用恰好一次。其中 $n$ 为给定的结点个数。返回值应为一个 $n$ 阶排列 $p$，其中 $p[i]$ 表示链上的第 $i + 1$ 个结点（正序或逆序都可以）。

你可以调用以下函数：

int query(std::vector<int> p);

其中 $p$ 应为一个 $n$ 阶排列，表示此次查询的链。

样例交互库将读入以下格式的输入数据：

第一行一个正整数 $n$。

接下来的一行为有 $n$ 个 $[1, n]$ 内的数，第 $i$ 个为链上第 $i$ 个点。

样例交互库将输出如下格式的输出数据：

若你进行了非法的查询（或查询次数 $> 2 \times 10^5$），样例交互库会输出 WA: 0；否则，若你正确返回了链的信息，会输出 AC: [你使用的查询次数] ，否则输出 WA: 1。

保证评测时交互库使用时间不超过 $\texttt{1s}$，空间不超过 $\texttt{256MB}$。

注意，最终使用的交互库不一定与样例交互库相同。

solve(3) // return: {3, 2, 1}

query({1, 2, 3}) // return: 2
query({3, 1, 2}) // return: 1
query({2, 3, 1}) // return: 1

对于 $100\%$ 的数据，$3 \leq n \leq 500$。

子任务 $1$ 共 $15$ 个测试点。

如果你的程序在任一测试点中未返回正确结果，则你会获得 $0$ 分；否则，你将获得 $10$ 分。

子任务 $2$ 共 $40$ 个测试点。

如果你的程序在任一测试点中未返回正确结果，则你会获得 $0$ 分；否则，你的分数将按如下方式计算（其中 $T$ 是你的最大查询次数）。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$

QOJ.ac