P17242 [IOI 2026] 方块游戏 / tiling
题目描述
Barchin 和 Charos 正在一个由 $2N\times 2M$ 正方形单元格组成的网格上玩游戏。从上到下，行的编号依次为 $0$ 到 $2N-1$；从左到右，列的编号依次为 $0$ 到 $2M-1$。对于 $0\le i
输入格式
```text
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]
```
输出格式
```text
R[0] C[0]
R[1] C[1]
...
R[NM-1] C[NM-1]
```
这里，$R[k]$ 和 $C[k]$ 是第 $k$ 次调用 `receive_block` 返回的一对整数。
说明/提示
### 例子
考虑一次游戏，其中 $N=1$，$M=2$，因此网格有 $2$ 行和 $4$ 列。评测程序首先调用：
```cpp
init(1, 2)
```
初始状态下，所有单元格均为空。网格如下所示：
:::align{center}
:::
需要放置 $N\cdot M=2$ 个方块。假设 Barchin 给出一个方块，其中包含三个黑色小方块和一个位于右上角的白色小方块。评测程序调用：
```cpp
receive_block(1, 0, 1, 1)
```
Charos 决定将此方块放置在网格的左侧，返回 $(0,0)$。
现在的网格看起来是这样的：
:::align{center}
:::
Barchin 随后给出另一个方块，其左上角为白色，其余三个小方块为黑色：
```cpp
receive_block(0, 1, 1, 1)
```
在剩余的网格单元格中，唯一行和列均为偶数且能作为 $2\times 2$ 方块左上角的单元格是 $(0,2)$，因此 Charos 返回 $(0,2)$。最终的网格如下所示：
:::align{center}
:::
因为没有 $2\times 2$ 方格被黑色小方块完全覆盖，所以 Charos 成功放置了所有方块，Barchin 始终未获胜。Charos 赢得游戏。
### 约束条件
对于每个方块，令 $S$ 为其包含的四个小方块中黑色小方块的数量。即
$$
S=TL+TR+BL+BR.
$$
- $1\le N,M\le 100$
- 对于每个方块，$0\le S\le 3$。
### 子任务
| 子任务 | 分数 | 额外的约束条件 |
|:--:|:--:|:--:|
| $1$ | $6$ | 每个方块的 $S=1$，且 $N=2$。 |
| $2$ | $16$ | 每个方块的 $S=3$。$N=M$，$N$ 为偶数，且四种可能的方块着色方案每一种都恰好出现 $\frac{N^2}{4}$ 次。 |
| $3$ | $10$ | 每个方块的 $S=1$。 |
| $4$ | $29$ | 每个方块的 $S\le 2$。 |
| $5$ | $39$ | 没有额外的约束条件。 |