P9324 [EGOI 2022] Chika Wants to Cheat / 出老千（通信题无法评测）

Day 2 Problem D. 题面译自 [EGOI2022 cheat](https://stats.egoi.org/media/task_description/2022_cheat_en.pdf)。翻译来自于 [ChatGPT](https://chatgpt.com/) 并进行人工校对，若有误请联系 [rui_er](https://www.luogu.com.cn/user/122461)。 [](https://creativecommons.org/licenses/by-sa/3.0/) 2s 512MB **本题是一道通信题，你的程序会被多次执行。**

Chika 有一副包含 $q$ 张牌的牌组，每张牌都用不同的正整数编号。她想用这些牌和 Shuchi'in Academy 学生会的朋友玩游戏，但她也想赢，所以她决定在自己的牌背面偷偷做记号。 这些牌都是大小为 $2\times 2$ 的正方形，其中左下角坐标为 $(0, 0)$，右上角坐标为 $(2, 2)$。Chika 在每张牌的背面画一个特定的图案，这样她以后可以通过观察图案知道牌正面写的是什么数字。她按照以下步骤画出这样的图案：她可以任意次数地（包括 $0$ 次）选择两个不同的相对于牌的左下角坐标为整数的点 $A$ 和 $B$，然后在它们之间画一条**直线段**。 Chika 只会画**有效**的线段，也就是说，两点 $A$ 和 $B$ 之间的线段上不能有不同于 $A$ 和 $B$ 的另一个坐标为整数的点 $C$。例如，从 $(0, 0)$ 到 $(2, 2)$ 的线段**无效**，因为它包含了点 $(1, 1)$，但从 $(0, 0)$ 到 $(1, 1)$ 的线段以及从 $(1, 1)$ 到 $(2, 2)$ 的线段都是**有效**的，并且 Chika 可以在同一个图案上同时画这两条线段。此外，注意线段是无方向的：从 $A$ 到 $B$ 画的线段与自身相同，也与反过来从 $B$ 到 $A$ 画的线段相同。 重要的是，Chika 希望确保她能够识别自己的牌，无论这些牌如何旋转。一张牌可以相对于原始方向逆时针旋转 $0$、$90$、$180$ 或 $270$ 度。 你的任务是帮助 Chika 设计 $q$ 张牌上的图案，并在之后识别出这些牌。 --- **交互方式** *这是一个分两个阶段的通信题，**每个阶段需要分别运行你的程序**。* 你需要实现两个函数： - 一个返回需要画在给定牌背面的图案的 `BuildPattern` 函数。该函数将在第一阶段被调用 $q$ 次。 - 一个返回携带第一阶段中画出的某图案的（可能已经旋转的）牌号的 `GetCardNumber` 函数。该函数将在第二阶段被调用 $q$ 次。 **第一个函数** ```cpp std::vector BuildPattern(int n); ``` 该函数接受一个参数 $n$，即写在牌正面的数字。你需要返回一个 `std::vector`，其中包含 Chika 为识别该牌而在其背面画出的图案所包含的线段。一条线段表示为一个点的 `std::pair`，每个点用它相对于牌左下角的整数坐标 $(x, y)$ 的 `std::pair` 表示，其中 $0\le x,y\le 2$。Chika 画出的所有线段都必须是有效的，并且两两不同。数据保证，对 `BuildPattern` 的所有 $q$ 次调用中，参数 $n$ 的值互不相同。 在收到 $q$ 张牌的所有图案后，评分程序可以对每个图案任意次数地执行以下任何操作： - 将整个图案逆时针旋转 $0$、$90$、$180$ 或 $270$ 度。 - 修改 `std::vector` 中的线段顺序。 - 修改图案中某条线段端点的顺序。（从 $A$ 到 $B$ 画出的线段可以变为从 $B$ 到 $A$ 的相同线段。） **第二个函数** ```cpp int GetCardNumber(std::vector p); ``` 该函数接受一个参数 $p$，即描述 Chika 在牌背面画出的图案的线段的 `std::vector`，它基于之前对你的 `BuildPattern` 函数的调用返回值。该函数必须返回写在牌正面的数字 $n$。请注意，图案 $p$ 不一定是 `BuildPattern` 返回的原始形式；它可能已经经过上述三种操作的修改。此外，牌的顺序也可能与第一阶段中提供的顺序不同，但数据保证每张牌正好被使用一次。

见【交互方式】部分。

见【交互方式】部分。

**样例交互过程** |函数调用|返回值|解释说明| |:-|:-|:-| |第一阶段开始||| |`BuildPattern(3)`|`{{{0, 0}, {2, 1}},{{1, 1}, {2, 0}}}`|我们需要给写有数字 $3$ 的牌设计一个图案。我们决定画两条线段：$(0,0),(2,1)$ 之间、$(1,1),(2,0)$ 之间。| |`BuildPattern(1)`|`{{{0, 1}, {0, 0}}}`|我们需要给写有数字 $1$ 的牌设计一个图案。我们决定画一条线段：$(0,1),(0,0)$ 之间。| |第一阶段结束||| |第二阶段开始||| |`GetCardNumber({{{0, 0}, {0, 1}}})`|`1`|我们得到一个画有一条线段的图案：$(0,0),(0,1)$ 之间。这和我们画出这条线段得到相同图案：$(0,1),(0,0)$ 之间。这和我们在 `BuildPattern` 第二次调用时返回的图案完全相同（旋转 $0$ 度）。因此，我们返回 $1$。| |`GetCardNumber({{{1, 1}, {2, 2}},{{1, 2}, {2, 0}}})`|`3`|我们得到一个画有一条线段的图案：$(1,1),(2,2)$ 之间、$(1,2),(2,0)$ 之间。这是我们在 `BuildPattern` 第一次调用时返回的图案逆时针旋转 $90$ 度后得到的图案。因此，我们返回 $3$。| |第二阶段结束||| --- **数据范围** 对于全部数据，$1\le q\le 10\ 000$，$1\le n\le 67\ 000\ 000$。可以证明存在一种构造图案的算法，可以识别出 $67\ 000\ 000$ 张不同的牌。 - 子任务一（$2$ 分）：$n\le 2$。 - 子任务二（$9$ 分）：$n\le 25$。 - 子任务三（$15$ 分）：$n\le 1\ 000$，并且交互库**不会旋转**图案。（交互库**可能**执行另外两种操作。） - 子任务四（$3$ 分）：$n\le 16\ 000\ 000$，并且交互库**不会旋转**图案。（交互库**可能**执行另外两种操作。） - 子任务五（$24$ 分）：$n\le 16\ 000\ 000$。 - 子任务六（$18$ 分）：$n\le 40\ 000\ 000$。 - 子任务七（$29$ 分）：无特殊限制。