P14351 [JOISC 2019] 矿物 / Minerals

在洛谷上提交本题，需要定义函数 `int Query(int x);`、`void Answer(int a, int b);` 而非引用头文件 `minerals.h`。

JOI 教授的实验室正在研究 $N$ 种矿物。每种矿物有 2 片样本，总共有 $2N$ 片样本，编号从 $1$ 到 $2N$。 某天，助手 Bitaro 不慎将装有这 $2N$ 片样本的盒子打翻，他已无法分辨哪两片样本属于同一种矿物。 实验室拥有一种设备，可通过测量每种矿物吸收的波长，来统计设备内当前包含的矿物种类数量。Bitaro 的任务是从 $2N$ 片样本中找出所有 $N$ 对同种矿物。初始时，设备内没有放入任何样本。Bitaro 可执行以下操作： - 将一片样本插入设备中，Bitaro 会得知设备内当前包含的矿物种类数量。 - 从设备中取出一片样本，Bitaro 会得知设备内当前包含的矿物种类数量。 为避免被 JOI 教授发现 Bitaro 惹出麻烦，他总共最多只能执行 $1\,000\,000$ 次操作。 请编写一个程序，给定矿物种类数 $N$，利用该设备，找出所有同种矿物的配对。 ### 实现细节 程序应实现以下函数： - `void Solve(int N)` 此函数在每个测试用例中**恰好被调用一次**。 - 参数 $N$ 表示矿物种类的数量。 你的程序可以调用以下函数： - `int Query(int x)` 对于你指定的样本编号 $x$，若该样本已在设备中，则将其取出；否则将其插入设备中。然后返回设备中当前包含的矿物种类数量。 - 你通过参数 $x$ 指定样本编号，必须满足 $1 \le x \le 2N$。否则，你的程序将被判定为 **Wrong Answer [1]**。 - 函数 `Query` 的调用次数不得超过 $1\,000\,000$ 次。否则，你的程序将被判定为 **Wrong Answer [2]**。 - `void Answer(int a, int b)` 使用此函数，你将输出同种矿物的配对。 - 参数 $a$ 和 $b$ 表示第 $a$ 片样本与第 $b$ 片样本属于同一种矿物。它们必须满足 $1 \le a \le 2N$ 且 $1 \le b \le 2N$。否则，你的程序将被判定为 **Wrong Answer [3]**。 - 若在 $a$ 或 $b$ 中，同一数值出现超过一次，你的程序将被判定为 **Wrong Answer [4]**。 - 若指定的样本属于不同种类的矿物，你的程序将被判定为 **Wrong Answer [5]**。 函数 `Answer` 必须**恰好被调用 $N$ 次**。若在函数 `Solve` 执行结束时，对 `Answer` 的调用次数不等于 $N$，你的程序将被判定为 **Wrong Answer [6]**。 ### 重要提示 - 你的程序可以为内部使用实现其他函数，或使用全局变量。 - 你的程序**不得**使用标准输入和标准输出，也不得通过任何方式与其他文件通信。但你的程序可以向 stderr 输出调试信息。 ### 编译与测试运行 你可以从竞赛网页下载一个归档文件，其中包含用于测试你程序的样例评测器。该归档文件还包含你程序的样例源代码文件。 样例评测器是文件 `grader.cpp`。为测试你的程序，请将 `grader.cpp`、`minerals.cpp` 和 `minerals.h` 放在同一目录下，并运行以下命令编译你的程序： ``` g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp ``` 当编译成功后，将生成可执行文件 `grader`。 请注意，实际评测器与样例评测器不同。样例评测器将以单进程方式运行，从标准输入读取输入数据，并将结果写入标准输出。

样例评测器从标准输入读取以下数据： $N$ $X_1\ Y_1$ $\vdots$ $X_N\ Y_N$ 其中，$X_i$ 和 $Y_i$（$1 \le i \le N$）表示第 $X_i$ 片样本与第 $Y_i$ 片样本属于同一种矿物。

当程序成功终止时，样例评测器将以下信息写入标准输出（引号仅用于清晰说明）： - 若你的程序被判定为正确，它将输出调用函数 `Query` 的次数，格式为 “Accepted: 100”。 - 若你的程序被判定为 **Wrong Answer**，它将输出其类型，格式为 “Wrong Answer [1]”。 若你的程序被判定为多种类型的 **Wrong Answer**，样例评测器仅报告其中一种。

### 样例 1 解释 | 调用 | 调用 | 返回值 | |:-------------:|:-------------:|:------:| | `Solve(4)` | | | | | `Query(1)` | 1 | | | `Query(2)` | 2 | | | `Query(5)` | 2 | | | `Query(2)` | 1 | | | `Answer(3, 4)`| （无） | | | `Answer(5, 1)`| （无） | | | `Answer(8, 7)`| （无） | | | `Answer(2, 6)`| （无） | ### 数据范围 关于 $X_i$ 和 $Y_i$ 的定义，请参阅“样例评测器的输入”部分。 - $1 \le N \le 43\,000$。 - $1 \le X_i \le 2N$（$1 \le i \le N$）。 - $1 \le Y_i \le 2N$（$1 \le i \le N$）。 - $X_i \ne X_j$（$1 \le i < j \le N$）。 - $Y_i \ne Y_j$（$1 \le i < j \le N$）。 - $X_i \ne Y_j$（$1 \le i \le N$，$1 \le j \le N$）。 ### 子任务 1. （6 分）$N \le 100$。 2. （25 分）$N \le 15\,000$，且对所有 $1 \le i \le N$，满足 $1 \le X_i \le N$，$N + 1 \le Y_i \le 2N$。 3. （9 分）$N \le 15\,000$。 4. （30 分）$N \le 38\,000$。 5. （5 分）$N \le 39\,000$。 6. （5 分）$N \le 40\,000$。 7. （5 分）$N \le 41\,000$。 8. （5 分）$N \le 42\,000$。 9. （10 分）无额外约束。