你最近学习了配交互库。
给定一条长度为 $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
数据范围与提示
子任务 $1$($10$ 分):$n \leq 30$。
子任务 $2$($90$ 分):$n \leq 500$。
对于 $100\%$ 的数据,$3 \leq n \leq 500$。
子任务 $1$ 评分方式
子任务 $1$ 共 $15$ 个测试点。
如果你的程序在任一测试点中未返回正确结果,则你会获得 $0$ 分;否则,你将获得 $10$ 分。
子任务 $2$ 评分方式
子任务 $2$ 共 $40$ 个测试点。
如果你的程序在任一测试点中未返回正确结果,则你会获得 $0$ 分;否则,你的分数将按如下方式计算(其中 $T$ 是你的最大查询次数)。
$T$ 的值 | 对应分数 |
---|---|
$2.5 \times 10^4 < T \leq 3 \times 10^5$ | $\frac{975000}{T}$ |
$8000 < T \leq 2.5 \times 10^4$ | $114 - \frac{3}{1000} T$ |
$T \leq 8000$ | $90$ |
时间限制:$\texttt{3s}$
空间限制:$\texttt{512MB}$