P9324 [EGOI 2022] Chika Wants to Cheat / Cheating (This communication task cannot be judged).

Day 2 Problem D. The statement is translated from [EGOI2022 cheat](https://stats.egoi.org/media/task_description/2022_cheat_en.pdf). The translation is from [ChatGPT](https://chatgpt.com/) and has been manually proofread. If there are any mistakes, please contact [rui_er](https://www.luogu.com.cn/user/122461)。 [](https://creativecommons.org/licenses/by-sa/3.0/) 2s 512MB **This is a communication task. Your program will be executed multiple times.**

Chika has a deck of $q$ cards, each card labeled with a distinct positive integer. She wants to play a game with her friends from the Shuchi'in Academy Student Council, but she also wants to win, so she decides to secretly mark the backs of her cards. Each card is a $2\times 2$ square, with the bottom-left corner at $(0, 0)$ and the top-right corner at $(2, 2)$. Chika draws a specific pattern on the back of each card so that later she can tell which number is on the front by looking at the pattern. She draws such a pattern using the following process: any number of times (including $0$), she chooses two different points $A$ and $B$ whose coordinates relative to the bottom-left corner of the card are integers, and then draws a **line segment** between them. Chika only draws **valid** segments. That is, the segment between points $A$ and $B$ must not contain any other integer-coordinate point $C$ different from $A$ and $B$. For example, the segment from $(0, 0)$ to $(2, 2)$ is **invalid** because it contains the point $(1, 1)$. However, the segment from $(0, 0)$ to $(1, 1)$ and the segment from $(1, 1)$ to $(2, 2)$ are both **valid**, and Chika may draw both segments in the same pattern. Also note that segments are undirected: the segment drawn from $A$ to $B$ is the same as the one drawn from $B$ to $A$. Importantly, Chika wants to ensure she can recognize her cards no matter how they are rotated. A card can be rotated counterclockwise by $0$, $90$, $180$, or $270$ degrees relative to its original orientation. Your task is to help Chika design the patterns on the $q$ cards and then recognize the cards later. --- **Interaction** *This is a two-phase communication task. **Your program must be run separately for each phase**.* You need to implement two functions: - A function `BuildPattern` that returns the pattern to be drawn on the back of a given card. This function will be called $q$ times in the first phase. - A function `GetCardNumber` that returns the number of a (possibly rotated) card carrying a pattern drawn in the first phase. This function will be called $q$ times in the second phase. **The first function** ```cpp std::vector BuildPattern(int n); ``` This function takes one parameter $n$, the number written on the front of the card. You must return a `std::vector` containing the segments in the pattern that Chika draws to recognize this card. A segment is represented as a `std::pair` of two points, and each point is represented as a `std::pair` of its integer coordinates $(x, y)$ relative to the bottom-left corner of the card, where $0\le x,y\le 2$. All segments drawn by Chika must be valid and pairwise distinct. The testdata guarantees that across all $q$ calls to `BuildPattern`, the values of $n$ are pairwise distinct. After receiving the patterns for all $q$ cards, the grader may apply any number of the following operations to each pattern: - Rotate the entire pattern counterclockwise by $0$, $90$, $180$, or $270$ degrees. - Reorder the segments in the `std::vector`. - Swap the endpoints of any segment in the pattern. (A segment drawn from $A$ to $B$ may become the same segment listed as from $B$ to $A$.) **The second function** ```cpp int GetCardNumber(std::vector p); ``` This function takes one parameter $p$, a `std::vector` of segments describing the pattern drawn on the back of a card, based on the return values of earlier calls to your `BuildPattern` function. This function must return the number $n$ written on the front of the card. Note that $p$ is not necessarily in the original form returned by `BuildPattern`; it may have been modified by the three operations above. Also, the order of cards may differ from the order in the first phase, but the testdata guarantees that each card is used exactly once.

See the “Interaction” section.

See the “Interaction” section.

**Sample interaction process** |Function call|Return value|Explanation| |:-|:-|:-| |Start of phase 1||| |`BuildPattern(3)`|`{{{0, 0}, {2, 1}},{{1, 1}, {2, 0}}}`|We need to design a pattern for the card labeled $3$. We decide to draw two segments: between $(0,0)$ and $(2,1)$, and between $(1,1)$ and $(2,0)$.| |`BuildPattern(1)`|`{{{0, 1}, {0, 0}}}`|We need to design a pattern for the card labeled $1$. We decide to draw one segment: between $(0,1)$ and $(0,0)$.| |End of phase 1||| |Start of phase 2||| |`GetCardNumber({{{0, 0}, {0, 1}}})`|`1`|We are given a pattern with one segment between $(0,0)$ and $(0,1)$. This is the same as the segment we drew between $(0,1)$ and $(0,0)$. This matches exactly the pattern we returned in the second call to `BuildPattern` (rotation by $0$ degrees). Therefore, we return $1$.| |`GetCardNumber({{{1, 1}, {2, 2}},{{1, 2}, {2, 0}}})`|`3`|We are given a pattern with two segments: between $(1,1)$ and $(2,2)$, and between $(1,2)$ and $(2,0)$. This is the pattern from the first call to `BuildPattern` after a $90$-degree counterclockwise rotation. Therefore, we return $3$.| |End of phase 2||| --- **Constraints** For all testdata, $1\le q\le 10\ 000$, $1\le n\le 67\ 000\ 000$. It can be proven that there exists a pattern construction algorithm that can distinguish $67\ 000\ 000$ different cards. - Subtask 1 ($2$ points): $n\le 2$. - Subtask 2 ($9$ points): $n\le 25$. - Subtask 3 ($15$ points): $n\le 1\ 000$, and the interaction library **will not rotate** the pattern. (The interaction library **may** perform the other two operations.) - Subtask 4 ($3$ points): $n\le 16\ 000\ 000$, and the interaction library **will not rotate** the pattern. (The interaction library **may** perform the other two operations.) - Subtask 5 ($24$ points): $n\le 16\ 000\ 000$. - Subtask 6 ($18$ points): $n\le 40\ 000\ 000$. - Subtask 7 ($29$ points): No special constraints. Translated by ChatGPT 5