QOJ.ac

QOJ

Total points: 100 Interactive

# 8363. interactive

Statistics

你最近学习了配交互库。

给定一条长度为 $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}$