题目描述

著名魔术师 Harry 又设计了一个轰动全场的新魔术。这一次，他不需要助手。

一开始有一副包含 $N$ 张正方形卡牌的牌，卡牌编号为 $1$ 到 $N$。观众从中选出 $Q$ 张牌，将它们打乱，然后一张一张地把牌背面对着魔术师展示。Harry 能够准确猜出每张牌的编号。起初观众十分惊讶，但过了一会儿，有人发现 Harry 在作弊。

展示卡牌的观众注意到，每张牌背面都有细小的标记，标记由若干条直线段组成。更准确地说，每张牌背面有一个大小为 $2\times 2$ 的区域用于画这些线段。我们在这个区域中建立坐标系：左下角为 $(0,0)$，右上角为 $(2,2)$。

每条线段的两个端点都是整数坐标点，并且端点不同。此外，每条线段上恰好只有两个整数坐标点，也就是它的两个端点。我们称这样的线段为合法线段。

Harry 还考虑到了卡牌可能被旋转展示的情况。即使卡牌相对于标记绘制时的方向被旋转，他的魔术仍然可以成功。

任务

你要再次证明魔术并不存在。因此，请编写程序 magic2，扮演魔术师 Harry：程序需要先根据给定卡牌编号画出标记，然后在之后根据看到的标记猜出卡牌编号。

实现细节

你需要实现两个函数，分别用于“根据卡牌编号画标记”和“根据标记猜卡牌编号”。函数格式如下：

std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> mark_card(int k);

int tell_card(std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> card);

为方便说明，下文把

std::pair<std::pair<int, int>, std::pair<int, int>>

称为一条线段。

mark_card

评测程序会调用 mark_card 共 $Q$ 次。每次调用有一个参数 $k$，表示卡牌编号，其中 $1\le k\le N$。

保证同一个测试中，传给 mark_card 的 $Q$ 个卡牌编号互不相同。

函数必须返回一个非空的线段列表，表示这张卡牌上的标记。每条线段由两个整数坐标点组成，每个坐标都在 $0$ 到 $2$ 之间。

返回的所有线段必须满足：

• 每条线段都是合法线段；
• 线段之间不能完全相同。

tell_card

评测程序会调用 tell_card 共 $Q$ 次。每次调用的参数是一张卡牌上的标记描述，格式与 mark_card 的返回值相同。

保证同一个测试中，tell_card 会按照之前 mark_card 被调用的相同顺序，依次接收到那 $Q$ 张卡牌的标记。

但是，在把标记传给 tell_card 之前，评测程序可能会对标记执行以下操作：

• 将整个标记逆时针旋转 $90^\circ$、$180^\circ$ 或 $270^\circ$；
• 改变线段在线段列表中的顺序；
• 对每条线段，交换它的两个端点的顺序。

因此，你的程序不能把信息编码在线段顺序或端点顺序中，而必须编码在所选择的线段集合本身中。

另外，mark_card 的调用和 tell_card 的调用会在你的程序的不同运行中完成，以保证这两个函数不能共享数据。

你的程序 magic2 可以包含其他辅助函数和全局变量，但这两个函数本身不应读标准输入或写标准输出。

Hydro OJ 提交说明

本题在 Hydro OJ 上采用通信题配置。你的提交代码需要实现上述两个函数，并在源文件末尾保留：

#include "grader.cpp"

也就是说，你提交的文件大致形如：

#include <bits/stdc++.h>
using namespace std;

using Point = pair<int, int>;
using Segment = pair<Point, Point>;

vector<Segment> mark_card(int k) {
    // 返回卡牌 k 的标记
}

int tell_card(vector<Segment> card) {
    // 根据标记返回卡牌编号
}

#include "grader.cpp"

请不要自己编写 main 函数。评测时，隐藏的 grader.cpp 会提供 main 并调用你的两个函数。

数据范围

• $1 \le N \le 6.7\times 10^7$；
• $1 \le Q \le 10^4$。

子任务

子任务	分值	依赖子任务	$N$	其他限制
1	2	-	$\le 2$	-
2	9	1	$\le 25$
3	15	-	$\le 10^3$	评测程序不会旋转标记，但可能执行另外两种操作
4	3		$\le 1.6\times 10^7$
5	24	1-4		-
6	18	1-5	$\le 4\times 10^7$
7	29	1-6	$\le 6.7\times 10^7$

一个测试通过，当且仅当程序遵守协议，并最终正确猜出所有卡牌编号。

示例通信

示例通信中共有两次查询，即 $Q=2$。

你的程序的动作	评测程序的动作
	mark_card(3)
return {{{0, 0}, {2, 1}}, {{1, 1}, {2, 0}}}
	mark_card(1)
return {{{0, 1}, {0, 0}}}
	评测程序将第一张标记逆时针旋转 $90^\circ$，并改变线段顺序和端点顺序。
	tell_card({{{0, 0}, {0, 1}}})
return 1
	tell_card({{{1, 1}, {2, 2}}, {{1, 2}, {2, 0}}})
return 3

下图展示了几种标记：第一幅图是卡牌 3 的原始标记；第二幅图是卡牌 3 被评测程序旋转 $90^\circ$ 后传入识别函数的标记；第三幅图是卡牌 1 的标记。

本地测试

压缩包中提供了 Lgrader.cpp。若你的程序文件为 magic2.cpp，可以在本地用如下命令测试：

g++ -std=c++17 -O2 magic2.cpp Lgrader.cpp -o local

本地测试程序会从标准输入读取：

• 第一行：一个正整数 $Q$，表示需要标记并识别的卡牌数量；
• 接下来 $Q$ 行：每行一个正整数 $k$，表示卡牌编号。

对于每张牌，本地测试程序会先获得你的标记，然后可能对其执行与正式评测相同的变换，最后把变换后的标记传给你的 tell_card。如果某张牌识别失败，会给出相应错误信息；否则会输出 Correctly guessed card k.，其中 $k$ 是卡牌编号。

@下发文件