这是一道交互题。
时隔半年,I 君的商店终于开不下去了,他决定转让商店,做一名探险家去探索未知的广阔世界。
根据古书记载,他在一个大荒漠的腹地找到了未知文明创造的地下宫殿,宫殿由 $N$ 个大型洞穴和 $M$ 条连接这些洞穴的双向通路构成。I 君能借助古书分辨所处的洞穴,但书中并没有记录 $M$ 条通路的连接结构,因此他难以搜寻传说中藏在宫殿里的无尽财宝。
不过现在 I 君发现了一个神秘机关,通过它可以获知宫殿的信息,I 君决定利用这个机关来得到宫殿的连接结构,请你来协助他。
题目描述
地下宫殿可以抽象成一张 $N$ 个点、$M$ 条边的无向简单图(简单图满足任意两点之间至多存在一条直接相连的边),洞穴从 $0 \sim n − 1$ 编号。目前你并不知道边有哪些。
每个洞穴都拥有一个光源,光源有开启、关闭两种状态,只有当光源处于开启状态时它所在的洞穴才会被照亮。初始时所有的光源都处于关闭状态,而光源的状态只能用 I 君发现的神秘机关改变。更具体的,使用神秘机关可以进行如下四种操作:
- 向机关给定一个编号 $x$,机关将会改变 $x$ 号洞穴,以及与 $x$ 号洞穴有通路直接相连的洞穴的光源状态。即原来开启的光源将会关闭;原来关闭的光源将会开启。
- 向机关给定一个编号 $x$,机关将会显示当前 $x$ 号洞穴光源的状态。
- 向机关给定两个编号 $x, y$,表示你确定有一条连接 $x$ 号洞穴与 $y$ 号洞穴的通路,并让机关记录。
- 向机关给定一个编号 $x$,机关将会判断与 $x$ 号洞穴相连的通路是否都已被记录。
机关在完成上一次操作后才能进行下一次操作。机关不能随意使用,因此每种操作的使用次数都有限制,分别为 $L_m, L_q, M, L_c$。你的任务是,编写一个程序,帮助 I 君决定如何合理利用神秘机关,从而正确地找到这 $M$ 条通路。
实现细节
你不需要,也不应该实现主函数,你只需要实现函数 $\texttt{explore(N, M)}$,这里的 $\texttt{N}$ 和 $\texttt{M}$ 分别表示洞穴和通路的个数。你可以通过调用
如下四个函数来和交互库进行交互:
- $\texttt{modify(x)}$
- 这个函数可以令机关执行操作 $1$,给定的编号为 $x$。
- 你需要保证 $0 \le x < N$,这个函数没有返回值。
- $\texttt{query(x)}$
- 这个函数可以令机关执行操作 $2$,给定的编号为 $x$。
- 你需要保证 $0 \le x < N$,这个函数返回 $0$ 或 $1$,表示目前 $x$ 号洞穴的光源为关闭($0$ 表示)或开启($1$ 表示)状态。
- $\texttt{report(x, y)}$
- 这个函数可以令机关执行操作 $3$,给定的编号为 $x, y$。
- 你需要保证 $0 \le x, y < N$ 且 $x \neq y$,这个函数没有返回值。
- $\texttt{check(x)}$
- 这个函数可以令机关执行操作 $4$,给定的编号为 $x$。
- 你需要保证 $0 \le x < N$,这个函数返回 $0$ 或 $1$,其中返回 $1$ 当且仅当与 $x$ 号洞穴相连的所有通路都已通过操作 $3$ 被记录。
评测时,交互库会恰好调用 $\texttt{explore}$ 一次。
本题保证所使用的图在交互开始之前已经完全确定,不会根据和你的程序的交互过程动态构造,因此题目中的交互操作都是确定性的,你不需要关心这些操作在交互库中的具体实现。
数据保证在调用次数限制下,交互库运行所需的时间不超过 1s;交互库使用的内存大小固定,且不超过 128MB。
实现方法
附加文件中已经提供了一个 template_explore.cpp/c/pas
,请将这个文件拷贝一份,重命名为 explore.cpp/c/pas
,然后在其基础上答题。
- 对 C++ / C 语言选手
- 请确保你的程序开头有
#include "explore.h"
。 - 你需要实现的函数 $\texttt{explore}$ 的接口信息如下:
- $\texttt{void explore(int N, int M);}$
- 你可以调用的交互函数的接口如下:
- $\texttt{void modify(int x);}$
- $\texttt{int query(int x);}$
- $\texttt{void report(int x, int y);}$
- $\texttt{int check(int x);}$
- 请确保你的程序开头有
- 对 Pascal 语言选手
- 注意:Pascal 的代码中实现接口的语法较为复杂,请选手直接在下发的
template_explore.pas
的基础上进行答题,而不是自己从头实现代码。 - 你需要实现的函数 $\texttt{explore}$ 的接口信息如下:
- $\texttt{procedure _explore(N, M : longint);}$
- 注意:这里的函数名称是 $\texttt{_explore}$ 而非 $\texttt{explore}$,如果使用 $\texttt{explore}$ 将导致编译失败。
- 你可以调用的交互函数的接口如下:
- $\texttt{procedure modify(x : longint);}$
- $\texttt{function query(x : longint) : longint;}$
- $\texttt{procedure report(x : longint; y : longint);}$
- $\texttt{function check(x : longint) : longint;}$
- 注意:Pascal 的代码中实现接口的语法较为复杂,请选手直接在下发的
测试程序方式
试题目录下的 grader.cpp/c
以及 graderhelperlib.pas
是我们提供的交互库参考实现,最终测试时所用的交互库实现与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。
- 对 C/C++ 语言的选手:
- 你需要在本题目录下使用如下命令编译得到可执行程序:
- 对于 C 语言:
gcc grader.c explore.c -o explore -O2 -lm
- 对于 C++ 语言:
g++ grader.cpp explore.cpp -o explore -O2 -lm
- 对于 C 语言:
- 你需要在本题目录下使用如下命令编译得到可执行程序:
- 对 Pascal 语言选手:
- 你需要在本题目录下使用如下命令编译得到可执行程序:
fpc grader.pas -o"explore" -O2
- 你需要在本题目录下使用如下命令编译得到可执行程序:
- 对于编译得到的可执行程序:
- 可执行文件将从标准输入读入以下格式的数据:
- 第一行包含三个整数 $L_m, L_q, L_c$,第二行包含两个整数 $N, M$,意义如题面描述。
- 接下来 $M$ 行,每行两个整数 $x, y$,描述一条连接 $x$ 号洞穴与 $y$ 号洞穴的通路。
- 读入完成之后,交互库将调用恰好一次函数 $\texttt{explore}$,用输入的数据测试你的函数。你的函数正确返回后,交互库会判断你的计算是否正确,若正确则会输出
Correct
和交互函数调用次数相关信息,否则会输出相应的错误信息。
- 可执行文件将从标准输入读入以下格式的数据:
假设可执行文件读入的数据为:
100 200 300
3 2
0 1
1 2
数据第一行的三个整数分别表示三种操作的调用次数限制,即 $\texttt{modify(x)}$ 调用次数不能超过 $100$,$\texttt{query(x)}$ 调用次数不能超过 $200$,$\texttt{check(x)}$ 调用次数不能超过 $300$。
数据第二行的两个整数分别表示洞穴数和通路条数,即 $N = 3 , M = 2$。
$\texttt{report(x, y)}$ 调用次数不能超过 $M$,该例子中即不超过 $2$ 次。
下面是一个正确的交互过程:
选手程序 | 交互库 | 说明 |
---|---|---|
调用$\texttt{explore(3, 2)}$ | 开始测试 | |
调用$\texttt{modify(1)}$ | 对$0$号洞穴做操作$1$ | |
调用$\texttt{query(2)}$ | 返回$0$ | 目前$2$号洞穴的光源状态是关闭 |
调用$\texttt{report(0, 1)}$ | 发现了通路$(0, 1)$并记录 | |
调用$\texttt{check(0)}$ | 返回$1$ | 与$0$号洞穴相关的通路都已被记录 |
调用$\texttt{report(2, 1)}$ | 发现了通路$(2, 1)$并记录 | |
运行结束并返回 | 向屏幕打印`Correct` | 交互结束,结果正确 |
评分方式
最终评测只会收取 explore.cpp/c/pas
,修改选手目录下其他文件对评测无效。
本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。
在上述条件基础上,在一个测试点中,你得到满分,当且仅当:
- 你的每次函数调用均合法,且调用 $\texttt{modify}$、$\texttt{query}$ 和 $\texttt{check}$ 的次数分别不超过 $L_m, L_q, L_c$。
- 由于 $\texttt{report}$ 的调用次数限制为 $M$,你的每次调用都必须记录一条新的且存在的边;即每次调用 $\texttt{report(x, y)}$ 时,应满足:有一条连接 $x$ 号洞穴和 $y$ 号洞穴的通路,且在这次调用之前从未调用过 $\texttt{report(x, y)}$ 或 $\texttt{report(y, x)}$。
- 你实现的函数 $\texttt{explore}$ 正常返回。
- 在 $\texttt{explore}$ 函数返回时,你已经通过调用 $\texttt{report}$ 记录了全部 $M$ 条通路。
限制与约定
本题共 $25$ 个测试点,每个测试点 $4$ 分。每个测试点的数据规模和相关限制见下表。
测试点编号 | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | 特殊性质 |
---|---|---|---|---|---|---|
$1$ | $3$ | $2$ | $100$ | $100$ | $100$ | 无 |
$2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | |
$3$ | $200$ | $200$ | $4\times 10^4$ | |||
$4$ | $300$ | $299$ | $9\times 10^4$ | |||
$5$ | $500$ | $499$ | $1.5\times 10^5$ | |||
$6$ | $59998$ | $N/2$ | $17N$ | $17N$ | $0$ | A |
$7$ | $99998$ | $18N$ | $18N$ | |||
$8$ | $199998$ | $19N$ | $19N$ | |||
$9$ | $199998$ | $19N$ | $19N$ | |||
$10$ | $99997$ | $N-1$ | $18N$ | $18N$ | B | |
$11$ | $199997$ | $19N$ | $19N$ | |||
$12$ | $99996$ | $10^7$ | $10^7$ | $2M$ | C | |
$13$ | $199996$ | |||||
$14$ | $199996$ | |||||
$15$ | $99995$ | D | ||||
$16$ | $99995$ | |||||
$17$ | $199995$ | |||||
$18$ | $1004$ | $2000$ | $5\times 10^4$ | 无 | ||
$19$ | $3000$ | |||||
$20$ | $3000$ | |||||
$21$ | $5\times 10^4$ | $2N$ | $10^7$ | |||
$22$ | $10^5$ | $2N$ | ||||
$23$ | $1.5\times 10^5$ | $2\times 10^5$ | ||||
$24$ | $2\times 10^5$ | $2.5\times 10^5$ | ||||
$25$ | $2\times 10^5$ | $3\times 10^5$ |
再次提醒,题目保证测试所使用的图在交互开始之前已经完全确定,而不会根据和你的程序的交互动态构造。
表中特殊性质栏中变量的含义如下:
- A:保证每个点的度数恰好为 $1$。
- B:保证对于每个 $x > 0$,存在恰好一个 $y < x$ 的 $y$ 使得 $x$ 号洞穴与 $y$ 号洞穴有通路直接相连。
- C:存在 $0 \sim N − 1$ 的一个排列 $p_0, p_1, \ldots , p_{N−1}$,使得对任意 $1 \le i < N$,存在一条连接洞穴编号分别为 $p_{i−1}$ 与 $p_i$ 的通路。
- D:保证图连通。
保证不存在点度数为 $0$。
时间限制:$2\texttt{s}$
空间限制:$512\texttt{MB}$
提示
你的程序可以通过判断传入的 $N$ 的个位来区分上述不同的数据类型。