#1313. 「NOI2019」I 君的探险

内存限制:512 MiB 时间限制:2000 ms 题目类型:交互
上传者: Quank123Wip

题目描述

这是一道交互题。

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++
  • C++ (NOI)
  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

题目背景

时隔半年,I 君的商店终于开不下去了,他决定转让商店,做一名探险家去探索未知的广阔世界。

根据古书记载,他在一个大荒漠的腹地找到了未知文明创造的地下宫殿,宫殿由 N 个大型洞穴和 M 条连接这些洞穴的双向通路构成。I 君能借助古书分辨所处的洞穴,但书中并没有记录 M 条通路的连接结构,因此他难以搜寻传说中藏在宫殿里的无尽财宝。

不过现在 I 君发现了一个神秘机关,通过它可以获知宫殿的信息,I 君决定利用这个机关来得到宫殿的连接结构,请你来协助他。

题目描述

地下宫殿可以抽象成一张 N 个点、 M 条边的无向简单图(简单图满足任意两点之间至多存在一条直接相连的边),洞穴从 0 \sim n − 1 编号。目前你并不知道边有哪些。

每个洞穴都拥有一个光源,光源有开启、关闭两种状态,只有当光源处于开启状态时它所在的洞穴才会被照亮。初始时所有的光源都处于关闭状态,而光源的状态只能用 I 君发现的神秘机关改变。更具体的,使用神秘机关可以进行如下四种操作:

  1. 向机关给定一个编号 x ,机关将会改变 x 号洞穴,以及 x 号洞穴有通路直接相连的洞穴的光源状态。即原来开启的光源将会关闭;原来关闭的光源将会开启。
  2. 向机关给定一个编号 x ,机关将会显示当前 x 号洞穴光源的状态。
  3. 向机关给定两个编号 x, y ,表示你确定有一条连接 x 号洞穴与 y 号洞穴的通路,并让机关记录。
  4. 向机关给定一个编号 x ,机关将会判断与 x 号洞穴相连的通路是否都已被记录

机关在完成上一次操作后才能进行下一次操作。机关不能随意使用,因此每种操作的使用次数都有限制,分别为 L_m, L_q, M, L_c 。你的任务是,编写一个程序,帮助 I 君决定如何合理利用神秘机关,从而正确地找到这 M 条通路。

实现细节

你不需要,也不应该实现主函数,你只需要实现函数 \texttt{explore(N, M)} ,这里的 \texttt{N} \texttt{M} 分别表示洞穴和通路的个数。你可以通过调用如下四个函数来和交互库进行交互:

  1. \texttt{modify(x)}
    • 这个函数可以令机关执行操作 1 ,给定的编号为 x
    • 你需要保证 0 \le x < N ,这个函数没有返回值。
  2. \texttt{query(x)}
    • 这个函数可以令机关执行操作 2 ,给定的编号为 x
    • 你需要保证 0 \le x < N ,这个函数返回 0 1 ,表示目前 x 号洞穴的光源为关闭( 0 表示)或开启( 1 表示)状态。
  3. \texttt{report(x, y)}
    • 这个函数可以令机关执行操作 3 ,给定的编号为 x, y
    • 你需要保证 0 \le x, y < N x \neq y ,这个函数没有返回值。
  4. \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,然后在其基础上答题。

  1. 对 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);}
  2. 对 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;}

测试程序方式

试题目录下的 grader.cpp/c 以及 graderhelperlib.pas 是我们提供的交互库参考实现,最终测试时所用的交互库实现与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。

  1. 对 C/C++ 语言的选手:
    • 你需要在本题目录下使用如下命令编译得到可执行程序:
      • 对于 C 语言:gcc grader.c explore.c -o explore -O2 -lm
      • 对于 C++ 语言:g++ grader.cpp explore.cpp -o explore -O2 -lm
  2. 对 Pascal 语言选手:
    • 你需要在本题目录下使用如下命令编译得到可执行程序:
      • fpc grader.pas -o"explore" -O2
  3. 对于编译得到的可执行程序:
    • 可执行文件将从标准输入读入以下格式的数据:
      • 第一行包含三个整数 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 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上,在一个测试点中,你得到满分,当且仅当:

  1. 你的每次函数调用均合法,且调用 \texttt{modify} \texttt{query} \texttt{check} 的次数分别不超过 L_m, L_q, L_c
  2. 由于 \texttt{report} 的调用次数限制为 M ,你的每次调用都必须记录一条新的且存在的边;即每次调用 \texttt{report(x, y)} 时,应满足:有一条连接 x 号洞穴和 y 号洞穴的通路,且在这次调用之前从未调用过 \texttt{report(x, y)} \texttt{report(y, x)}
  3. 你实现的函数 \texttt{explore} 正常返回。
  4. \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 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
10 99997 N-1 18N 18N B
11 199997 19N 19N
12 99996 10^7 10^7 2M C
13 199996
14
15 99995 D
16
17 199995
18 1004 2\times 10^3 5\times 10^4
19 3\times 10^3
20
21 5\times 10^4 2N 10^7
22 10^5
23 1.5\times 10^5 2\times 10^5
24 2\times 10^5 2.5\times 10^5
25 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:保证图连通。

提示:你的程序可以通过判断传入的 N 的个位来区分上述不同的数据类型。