#3041. 「JOISC 2019 Day4」矿物

内存限制:256 MiB 时间限制:1000 ms 题目类型:交互
上传者: everlasting

题目描述

题目译自 JOISC 2019 Day4 T3「鉱物 / Minerals

JOI 教授的实验室正在研究 N 种矿物。每种矿物有两个样本,一共有 2N 个样本,编号为 1\sim 2N

一天,助手 Bitaro 不小心弄掉了这个装有 2N 个样本的箱子,他不知道哪两个样本是同一种矿物的样本了。

这个实验室有一台设备,可以通过测量每种矿物吸收光的波长,统计出插入这个设备的矿石种类数。Bitaro 决定利用这台设备给这 2N 个样本中属于相同矿石种类的两两配对。起初,设备中没有矿石样本。Bitaro 可以如下操作:

  • 向设备中插入一个矿石样本,Bitaro 可以知道设备中有多少种矿石样本;
  • 从设备中拔出一个矿石样本,Bitaro 可以知道设备中有多少种矿石样本;

这样 JOI 教授就不会找 Bitaro 的麻烦了。Bitaro 总共可以操作最多 10^6 次。

给出矿物种类数,写一个程序,利用这台设备给相同矿物种类样本配对。

实现细节

你需要提交一个文件,包含 minerals.h 并使用以下函数:

void Solve(int N)

对于每组数据,这个函数调用且仅调用一次。参数 N 代表 N ,即矿物种类数。

你的程序可以调用以下函数:

int Query(int x)

对于你指定的样本编号,如果设备中有这个样本,则将其抽出,否则将其插入,返回设备中矿石样本种类数。

  • 对于你通过参数 x 指定的样本编号 x ,必须保证 1\le x\le 2N ,否则程序将被判为 Wrong Answer [1]
  • Query() 函数不能调用超过 10^6 次,否则程序将被判为 Wrong Answer [2]
void Answer(int a, int b)

利用这个函数,你可以回答相同矿石种类的矿石样本编号,意味着 a b 号样本矿石种类相同。必须保证 1\le a,b\le 2N ,否则程序将被判为 Wrong Answer [3];如果重复回答同一对矿石,将被判为 Wrong Answer [4],如果 a b 并不属于同一种矿石,将被判为 Wrong Answer [5]

Answer() 函数必须被调用 N 次,否则程序将被判为 Wrong Answer [6]

输入格式

交互程序从标准输入中读入以下内容:

第一行一个正整数 N ,表示矿石种类数;

接下来 N 行,每行两个正整数 X_i,Y_i ,表示编号为 X_i Y_i 的矿石种类相同。

输出格式

交互程序将向标准输出输出以下内容:

如果你的程序正确,将输出 Accepted: 100

否则,将输出类似 Wrong Answer [1] 的内容。如果有多种错误,程序将只输出一个。

样例

样例输入

4
1 5
2 6
3 4
7 8

样例交互过程

调用 返回值
\texttt{Solve}(4)
\texttt{Query}(1) 1
\texttt{Query}(2) 2
\texttt{Query}(5) 2
\texttt{Query}(2) 1
\texttt{Answer}(3,4) (无)
\texttt{Answer}(5,1)
\texttt{Answer}(8,7)
\texttt{Answer}(2,6)

数据范围与提示

对于全部数据, 1\le N\le 4.3\times 10^4,1\le X_i,Y_i\le 2N ,保证每一个数对两两本质不同。

详细子任务附加条件及分值如下表:

子任务 附加限制 分值
1 N\le 100 6
2 N\le 1.5\times 10^4,1\le X_i\le N,N+1\le Y_i\le 2N\ (1\le i\le N) 25
3 N\le 1.5\times 10^4 9
4 N\le 3.8\times 10^4 30
5 N\le 3.9\times 10^4 5
6 N\le 4\times 10^4
7 N\le 4.1\times 10^4
8 N\le 4.2\times 10^4
9 无附加限制 10