题目描述

这是一道交互题。

在交互库中生成了一个长度为 $n$ 的排列 $A$，你需要实现一个函数 query_permutation 来得到这个排列。

int query_permutation(int n, int ans[]);

参数与返回值含义如下：

• n：排列 $A$ 的长度，保证 $n\ge 1$。
• ans：一个 int 数组。你需要把你得到的排列 $A$ 的第 $i$ 项存到 ans[i] 中作为结果，其中 $1\le i\le n$，并返回 1。
• 如果你发现无论如何都无法唯一确定排列 $A$，那么就返回 0。

你可以使用四个函数 new_round、next_step、addedge、query 来帮助你确定这个排列。

void new_round();
void next_step();
void addedge(int u, int v);
int query(int u, int v);

函数说明

new_round()

调用这个函数后，将开始新的一轮实验，新的实验默认阶段为 $1$。

next_step()

调用这个函数后，实验将进入下一个阶段。

addedge(u,v)

这个函数只能在每一轮实验的第一个阶段使用，表示在第 $u$ 个点和第 $v$ 个点之间连一条边。

如果 $u$ 或者 $v$ 不在范围 $[1,n]$ 之内，这次操作将会被忽略。

query(u,v)

将返回 $u+n$ 和 $v+n$ 的连通性。如果连通则返回 1，否则返回 0。

如果 $u$ 或者 $v$ 不在范围 $[1,n]$ 之内，将会返回 0。

交互过程说明

当你调用函数 new_round 的时候，将开始一轮新的实验。

这时交互库中会生成一个 $2n$ 个点的无向图。初始状态下有 $n$ 条边，第 $i$ 条边连接了点 $i$ 和点 $A_i+n$。

每一轮实验可以分成两个阶段：

1. 这个阶段在调用 new_round 后自动进入，你只能在每一轮实验的这个阶段内调用函数 addedge。每当你调用一次函数 addedge(u,v)，交互库将在图中的第 $u$ 个点和第 $v$ 个点之间连上一条无向边。如果在这个阶段内调用了函数 next_step，那么将会进入第二个阶段。这个阶段内不允许调用函数 query 和 new_round。
2. 你只能在每一轮实验的这个阶段内调用函数 query。每当你调用一次函数 query(u,v)，交互库将返回图中第 $u+n$ 个点和第 $v+n$ 个点之间的连通性。如果在这个阶段内调用了函数 new_round，将会重新开始一轮新的实验。这个阶段不允许调用函数 addedge 和 next_step。

如果你已经得到了答案，那么你可以在任意一轮实验的任意一个阶段返回答案。

实验最多进行两轮，即你最多只能调用两次函数 new_round。注意：程序开始必须调用一次 new_round。

你需要尽可能地减少函数 query 的调用次数。

交互库不是 adaptive 的，也就是说排列在一开始就确定。

实现细节

你需要包含头文件：

#include "per.h"

你需要实现：

int query_permutation(int n, int ans[]);

交互库提供的函数接口如下：

void new_round();
void next_step();
void addedge(int u, int v);
int query(int u, int v);

评测方式

评测系统将读入如下格式的输入数据：

1. 第一行：一个正整数 $T$，表示数据组数。
2. 每组数据的第 $1$ 行：一个正整数 $n$。
3. 每组数据的第 $2$ 行：$n$ 个正整数，第 $i$ 个整数表示 $A_i$。

对每组测试数据都会调用一次函数 query_permutation，并且评测系统都会输出两行：

• 第一行是四个空格隔开的整数，分别表示你的调用过程是否合法（如果合法输出 1，否则输出 0）、你的返回值、query 函数的调用次数以及 addedge 函数的调用次数。
• 第二行是 $n$ 个空格隔开的整数，表示你找到的排列 $A$。如果你的函数返回值是 0，那么这 $n$ 个数都将是 0。

样例输入 #1

2
3
2 1 3
2
1 2

样例输出 #1

1 1 6 2
2 1 3
1 0 0 0
0 0

样例解释 #1

对于第一组数据：

第一轮实验我们采取如下操作方式：在第一阶段连上边 $(1,2)$，然后在第二阶段两两查询连通性，我们发现此时的连通块是 $\{4,5\}$ 和 $\{6\}$。

第二轮实验我们采取如下操作方式：在第一阶段连上边 $(2,3)$，然后在第二阶段两两查询连通性，我们发现此时的连通块是 $\{4,6\}$ 和 $\{5\}$。

由此可以推出原来的排列是：

$$2,\ 1,\ 3$$

此时我们确定了一个排列，所以函数的返回值是 1。在整个过程中调用了 $2$ 次函数 addedge 和 $6$ 次函数 query。

数据范围与评分

对于所有数据，保证：

$$n\ge 1,\qquad T\le 10$$

对于每一个测试点，你的程序必须满足如下条件，才能获得分数：

• 对于每一组数据，函数调用都是合法的。
• 对于每一组数据，query 函数和 addedge 函数的调用次数都不会超过 $2\times 10^6$ 次。

对于前 $7$ 个子任务：

若 query 的次数不超过 $2\times 10^6$，则获得全部分数。

对于第 $8$ 个子任务：该子任务共包含 $3$ 个测试点。

若 query 的次数不超过 $0.98\times 10^6$，则获得全部分；否则会根据 query 的调用次数评分。设子任务中，所有测试点中所有 $10$ 组数据中最大 query 调用次数为 $c$，分数如下：

$c$	分数
$[1.55\times 10^6,2\times 10^6]$	$15$
$[1.15\times 10^6,1.55\times 10^6]$	$30-15\cdot\dfrac{c-1.15\times 10^6}{0.40\times 10^6}$
$[1.05\times 10^6,1.15\times 10^6]$	$45-15\cdot\dfrac{c-1.05\times 10^6}{0.10\times 10^6}$
$[0.98\times 10^6,1.05\times 10^6]$	$55-10\cdot\dfrac{c-0.98\times 10^6}{0.07\times 10^6}$

子任务

子任务编号	$n$	子任务分值
1	$=4$	5
2	$=5$
3	$=990$	7
4	$=1000$
5	$=4950$
6	$=5000$
7	$=5050$
8	$\le 10000$	55

下发文件中包含 grader.cpp 和 per.cpp 做参考。

@下发文件