P11090 [ROI 2021] Spy Game (I/O Interactive + Communication, No testdata yet) (Day 1)

Translated from [ROI 2021 D1T3](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day1.pdf). **This is an I/O interactive + communication problem**. A spy has obtained an important message and needs to pass it to headquarters. Since the message is very important, the spy decides to disguise the transmission as a popular game. The rules of the game are very simple. On a square board of size $n \times n$, initially no cell is colored. Two players take turns making moves. In one move, a player may choose any uncolored cell, and then color all currently uncolored cells inside the rectangle bounded by the chosen cell’s bottom-left corner and the top-right corner of the whole board (see the figure below). The player who colors the bottom-left cell of the board loses the game.  The spy will play on a website that provides games against an AI. The AI moves as follows: each time, the AI uniformly at random chooses one move among those moves that would color at most $k$ new cells (the random range does not include the bottom-left cell). Of course, if the bottom-left cell is the only possible choice, the AI will choose to color that cell and lose the game. The spy may play any number of games, but to hide their identity, it is better to play as few games as possible. Also, to look more natural, it is better to win as many games as possible. By recording the moves in all played games, the spy needs to transmit an important message. You need to write a program that will be run twice (solving two tasks). In the first run (Task 1), the program plays the role of the spy, plays several games against the AI, and at the same time transmits the secret message. In the second run (Task 2), only the list of moves from these games is given, and the program must reconstruct the secret message.

The first line of the input contains a number $1$ or $2$, indicating which run it is (the task number). In both the first and the second run, the second line contains three integers: $n$, the size of the board (in all test points, $n = 32$), $k$, the maximum number of cells the robot can color in one move (in all test points, $k = 8$), and $m$, the length of the secret message (in characters) (except for the samples, in all test points $m = 100000$). ### In Task 1: The third line contains the secret message: a string of length $m$ consisting of characters `0` and `1`. After reading it, your program should start interacting with the interactive library that implements the AI strategy, alternating moves with it. Each move is given as a pair of numbers: the column and row of the chosen cell. Columns are numbered from $1$ to $n$ from left to right, and rows are numbered from $1$ to $n$ from bottom to top (see the figure in the statement). The chosen cell must not have been colored before; otherwise the interaction will be terminated and the result for this test will become WA. When one of the players makes move `1 1`, the game ends, and the next game starts immediately. In the first game, your program moves first; in the second game, your program moves second; and so on. At the start of a new game, if your program believes that the number of games already played is sufficient to transmit a message of length $m$ and no further moves are needed, it should output a single number $0$ to terminate the interaction. If at that moment the AI is to move first, its first move will not be recorded in the log for the second run. You may not terminate the interaction in the middle of a game. If in the first run the program follows the rules for some number of games and satisfies the time and memory limits, then it will be run again for the second run. Otherwise, the second run will not happen, and the result of the first run (`WA`, `RE`, `TLE`, `MLE`, or `OLE`) will be the result for the test. ### In Task 2: The third line contains the number of games played in the first run. Then, in the order the games were played, the list of all moves made in all games will be given, including both your program’s moves and the interactive library’s moves. In the second run, your program must output a string of length $m$ consisting of `0` and `1`, representing the secret message. You must first read **all input** from standard input, and only then output the answer. If the result of the second run is `RE`, `TLE`, `MLE`, or `OLE`, then that result will be the result for the test. Otherwise, the output of your program will be checked. If it matches the secret message that was given to your program in the first run, the result will be `AC`; otherwise it will be `WA`.

After each output, print a newline and flush the output stream. If you use `cout

The sample above is only for understanding the input and output formats. In particular, note that in the given sample, the spy does not necessarily transmit any information in any way using the given sequence of steps. In the sample, blank lines are used to format the input and output. In actual interaction, you should print a newline after each query, but you do not need to print blank lines. The program will be run on $10$ test points, and each test point is worth up to $10$ points. In each test point there is one secret message of length $m = 100,000$. In each test point, the message is generated by a random number generator, and each character is independently chosen to be `0` or `1` with equal probability. The interactive library’s moves in each test are random and follow the description in the statement. However, on repeated runs, if the contestant program makes the same moves, the interactive program will also make the same moves in that test. If the program cannot correctly recover the message in the second run, or violates the rules in the first run, then this test will score $0$ points. Otherwise, the score of a test point depends on the number of games played in the first run and the number of games won. Let $W$ indicate whether you lose no more than one game (if you lose more than one game, then $W = 0$, otherwise $W = 1$), let $G$ be the number of games played, and let $B = \frac{m} {G}$ be the average number of secret bits transmitted per game. The number $b_i$ denotes the value of $B$ required to get $i$ points, and is given in the table below.  If $B > b_9$, you will get $W + 9$ points. Otherwise, let $s$ be such that $b_s \le B < b_{s+1}$; in this case, you will get $W + s + \frac{B−b_s} {b_{s+1}−b_s}$ points. The scores of individual tests are summed up, and the final total score is rounded to the nearest integer. This problem currently has no testdata. One possible way to implement such a communication problem on Luogu is: Task 1 uses I/O interaction, and Task 2 directly calls a function (but it may still require anti-cheating measures). The data files for this problem have been placed in the attachments (the input and output files have been manually renamed to `.in` and `,out` files), so you can test by yourself, and you are also welcome to provide an interactive library. Translated by ChatGPT 5