QOJ.ac

QOJ

Total points: 100 Interactive
[+2]

# 8363. interactive

Statistics

你最近学习了配交互库。

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

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

试在不超过 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

数据范围与提示

  • 子任务 110 分):n30

  • 子任务 290 分):n500

对于 100% 的数据,3n500

子任务 1 评分方式

子任务 115 个测试点。

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

子任务 2 评分方式

子任务 240 个测试点。

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

T 的值 对应分数
2.5×104<T3×105 975000T
8000<T2.5×104 11431000T
T8000 90

时间限制:3s

空间限制:512MB