P17242 [IOI 2026] Tiling Game

Barchin and Charos are playing a game on a grid of $2N\times 2M$ unit square cells. The rows are numbered $0$ to $2N −1$ from top to bottom, and the columns are numbered $0$ to $2M −1$ from left to right. For $0 \leq i < 2N$ and $0 \leq j

``` N M TL[0] TR[0] BL[0] BR[0] TL[1] TR[1] BL[1] BR[1] ... TL[NM-1] TR[NM-1] BL[NM-1] BR[NM-1] ```

``` R[0] C[0] R[1] C[1] ... R[NM-1] C[NM-1] ``` Here, $R[k]$ and $C[k]$ are the pair of integers returned by the k-th call to receive_block.

### Example Consider a game with $N = 1$ and $M =2$, so the grid has $2$ rows and $4$ columns. The grader first calls: ``` init(1, 2) ``` Initially, all cells are empty. The grid looks like this: :::align{center}  ::: There are $N\cdot M=2$ blocks to place. Suppose Barchin gives a block with three black tiles and one white tile at the top-right corner. The grader calls: ``` receive_block(1, 0, 1, 1) ``` Charos decides to place this block at the left side of the grid by returning $(0,0)$. The grid now looks like this: :::align{center}  ::: Barchin then gives another block with three black tiles and one white tile at the top-left corner: ``` receive_block(0, 1, 1, 1) ``` The only remaining cell with even row and even column that can serve as the top-left corner of a $2\times2$ block is $(0,2)$, so Charos returns $(0,2)$. The grid ends up like this: :::align{center}  ::: No $2\times2$ square is completely covered by black tiles, so Charos has successfully placed all blocks without Barchin ever winning. Charos wins the game. ### Constraints For each block, let $S$ be the number of black tiles among its four tiles. That is $S =TL+TR+BL+BR$. - $1 \leq N,M \leq100$ - $0 \leq S \leq3$ for every block. ### Subtasks ::cute-table{tuack} | Subtask | Score | Additional Constraints | |:--:|:--:|:--:| | $1$ | $6$ | $S=1$ for every block, and $N=2$. | | $2$ | $16$ | $S=3$ for every block. $N=M$，$N$ is even, and each of the four possible block colorings appears exactly $\frac{N^2}{4}$ times. | | $3$ | $10$ | $S=1$ for every block. | | $4$ | $29$ | $S\le 2$ for every block. | | $5$ | $39$ | No additional constraints. |