你最近学习了配交互库。
给定一条长度为 n−1 的链,结点的标号为一个 [1,n] 的排列。
每次,你可以查询这 n 个点上的一条长为 n−1 的链,交互库会返回这两条链公共的无向边数。
试在不超过 3×105 次查询内确定这条链。进一步地,你的得分和你所使用的查询次数有关。
注意:交互库不是自适应的,换言之,链在交互开始前就是确定的。
任务
你必须引用 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×105),样例交互库会输出 WA: 0
;否则,若你正确返回了链的信息,会输出 AC: [你使用的查询次数]
,否则输出 WA: 1
。
保证评测时交互库使用时间不超过 1s,空间不超过 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≤30。
子任务 2(90 分):n≤500。
对于 100% 的数据,3≤n≤500。
子任务 1 评分方式
子任务 1 共 15 个测试点。
如果你的程序在任一测试点中未返回正确结果,则你会获得 0 分;否则,你将获得 10 分。
子任务 2 评分方式
子任务 2 共 40 个测试点。
如果你的程序在任一测试点中未返回正确结果,则你会获得 0 分;否则,你的分数将按如下方式计算(其中 T 是你的最大查询次数)。
T 的值 | 对应分数 |
---|---|
2.5×104<T≤3×105 | 975000T |
8000<T≤2.5×104 | 114−31000T |
T≤8000 | 90 |
时间限制:3s
空间限制:512MB