UOJ Logo Universal Online Judge

UOJ

#153. 【UR #10】世界线

统计

picks 博士轻松地做出了魔仙堡女王的题目,并利用巴拉拉能量成功地修好了时光机器。但是这时他发现他已经迷失在了无数条世界线里,难以回到他原来处在的世界线的过去了。

为了回到正确的过去,picks 博士观测了 $n$ 个过去和 $n$个未来。经过 picks 博士的研究,他发现存在一个 1 到 $n$ 的排列 $A$,使得对于每一个 $i$ 都存在一条世界线连接着第 $i$ 个过去和第 $A_i$ 个未来。现在 picks 博士想要通过实验得到排列 $A$。

任务

因为有关世界线的理论非常复杂,所以 picks 博士的实验同样非常繁琐——他甚至用了不止一轮实验才得到了答案。但是我们可以把实验过程简化得到一道这样的题目:

这是一道交互题,在交互库中生成了一个长度为 $n$ 的置换 $A$,你需要编写一个函数 query_permutation 来得到这个置换,题面比较长,请大家耐心阅读

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

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

  • 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。

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

picks 博士的巴拉拉能量是有限的,因此为了节约能源,他规定实验最多进行两轮,即你最多只能调用两次函数 new_round(注意:程序开始必须调用一次new_round)。

同时,picks博士发现调用函数 query 也是会消耗巴拉拉能量的,因此他想让你尽可能地减少函数 query 的调用次数。

实现细节

本题只支持 C/C++/Pascal。

你只能提交一个源文件实现如上所述的 query_permutation 函数,并且遵循下面的命名和接口。

C/C++

你需要包含头文件 worldline.h。

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

函数 new_round, next_step, addedge, query 的接口信息如下。

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

Pascal

你需要使用单元 graderhelperlib。

function query_permutation(n: longint; var ans: array of longint) : longint;

函数 new_round, next_step, addedge, query 的接口信息如下。

procedure new_round;
procedure next_step;
procedure addedge(u, v: longint);
function query(u, v: longint): longint;

如果有不清楚的地方,见样例及测评库下载,内附了样例程序,样例程序按照样例一的解释调用函数

如果你不会本地调试交互题,可以点开UOJ的FAQ。

评测方式

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

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

对每组测试数据我们都会调用一次函数 query_permutation,并对每组测试数据评测系统都会输出两行:

第一行是四个空格隔开的整数,分别表示你调用函数过程是否合法(如果合法输出1,否则输出0),你的返回值,query 函数的调用次数以及 addedge 函数的调用次数。

第二行是 $n$ 个空格隔开的整数,表示你找到的排列 $A$,如果你的函数的返回值是 $0$,那么这 $n$ 个数都将是 $0$。

样例一

input

2
3
2 1 3
2
1 2

output

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

explanation

对于第一组数据:

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

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

由此我们可以推导出原来的排列是 $2\ 1\ 3$。此时我们确定了一个排列,所以函数的返回值是 $1$。在整个过程中调用了 $2$ 次函数 addedge 和 $6$ 次函数 query。

对于第二组数据:

我们发现此时无论怎么进行实验,都无法区分排列 $1\ 2$ 和排列 $2\ 1$,所以返回 $0$。

样例二

见样例数据下载。

限制与约定

共 $10$ 个测试点,每个测试点 $10$ 分。

对于每一个测试点,你得程序必须满足如下条件,才能获得 $10$ 分,否则得 $0$ 分:

  1. 对于每一组数据,函数调用都是合法的。
  2. 对于每一组数据,query 函数和 addedge 函数的调用次数都不会超过 $2 \times 10^6$ 次。
测试点编号$n$ 的规模
1$n = 4$
2$n = 5$
3$n = 990$
4$n = 1000$
5$n = 4950$
6$n=5000$
7$n=5050$
8$n \leq 10000$
9
10

对于所有数据,保证有 $n \geq 1,T \leq 10$,以上的 $10$ 个测试点都满足 $T=10$。

如果这题场上有人 AC,那么我们会给所有在比赛时通过了这题的选手中,后三个点调用 query 函数总数最少的人赠送萌萌哒 UOJ 抱枕一个!

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载