AT_agc077_e [AGC077E] Hamiltonian Path Inversion

> 现在请你在一个 $4\times 500$ 的网格图的每个顶点上写上 $0$ 或 $1$。请设计写法，使得对于每一个 $N=0,1,\ldots,999899,999900$，都满足以下条件： > > - 存在一条哈密顿路径（Hamiltonian path），使得按路径顺序经过顶点所得到的数字序列的逆序对数恰好为 $N$。 > >  > 这是一个 $3\times 4$ 的例子。通过这种写法，可以实现 $N=10, 11, \ldots, 20$ 的所有取值。 --- 本题为**交互题**。**本题参数为 $H=4,W=500,Q=200$，为固定常数。** 你和评测机会按照以下步骤进行交互。整体步骤分为第 $1$ 阶段和第 $2$ 阶段，第 $1$ 阶段先进行，之后立刻进入第 $2$ 阶段。 （第 $1$ 阶段） 输出一个 $H\times W$ 的矩阵 $A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W)$，矩阵元素为 $0$ 或 $1$。 （第 $2$ 阶段） 你需要解决如下子任务 $Q$ 次。 > 评测机会给出一个整数 $N$。 > 考虑在一个有 $H$ 行 $W$ 列的网格上，第 $i$ 行第 $j$ 列的格子上写有数 $A_{i,j}$。 > 找到一条长度为 $HW$ 的路径 $P$，从任意格子出发，每次走到相邻格子（上下左右之一），遍历所有 $HW$ 个格子且每个格子只访问一次，并允许以任意格子作为终点。要求满足： > > - 按照 $P$ 路径依次经过的格子所对应数字所构成的长度为 $HW$ 的序列，其逆序对数恰好为 $N$。

首先，标准输入给出 $H,W,Q$。 > $H\ W\ Q$ （第 $1$ 阶段） 你需要输出 $H$ 行，每行一个由 $0$ 和 $1$ 组成的字符串，长度为 $W$，表示 $A$ 矩阵的每一行。 > $A_{1,1}A_{1,2}\ldots A_{1,W}$ > $A_{2,1}A_{2,2}\ldots A_{2,W}$ > $\vdots$ > $A_{H,1}A_{H,2}\ldots A_{H,W}$ （第 $2$ 阶段） 你需要重复解决下面的问题共 $Q$ 次。每次评测机会给出一个整数 $N$。 > $N$ （注意：如果你的上一轮输出错误，则本轮会收到 $-1$ 作为输入。如果收到 $-1$，请立刻正常结束程序。若在第 $Q$ 次输出后第一次出错，之后不会再有输入。） 然后你需要输出一条哈密顿路径，其中第 $i$ 个经过的格子为 $(x_i, y_i)$，格式如下： > $x_1\ y_1$ > $x_2\ y_2$ > $\vdots$ > $x_{HW}\ y_{HW}$ 每个 $x_i, y_i$ 需满足： - $1\leq x_i\leq H,\ 1\leq y_i\leq W$。 - $(x_i, y_i)\neq (x_j, y_j)$，当 $i\neq j$。 - $|x_i-x_{i+1}|+|y_i-y_{i+1}|=1,\ \forall i=1,2,\ldots,HW-1$。 - 按照 $(A_{x_1,y_1}, A_{x_2,y_2}, \ldots, A_{x_{HW},y_{HW}})$ 形成的序列逆序对数恰为 $N$。

详见输入格式。在第 $1$ 阶段，输出 $H$ 行字符串，每行长度为 $W$。 在第 $2$ 阶段，每一次询问输出 $HW$ 行，每行两个整数，分别表示路径经过的格子的行和列编号。每次输出后请务必刷新输出流。

### 交互说明 本题为交互题。 首先，标准输入给出 $H,W,Q$。 > $H\ W\ Q$ （第 $1$ 阶段） 你需要输出一个 $H\times W$ 的矩阵 $A=(A_{i,j})$，矩阵元素取 $0$ 或 $1$，共 $H$ 行。 第 $i$ 行应输出 $A_{i,1}A_{i,2}\ldots A_{i,W}$，即一行长度为 $W$ 的由 `0`、`1` 构成的字符串。 > $A_{1,1}\ldots A_{1,W}$ > $A_{2,1}\ldots A_{2,W}$ > $\vdots$ > $A_{H,1}\ldots A_{H,W}$ （第 $2$ 阶段） 你将重复处理 $Q$ 次询问。每次评测机会输入一个整数 $N$。 > $N$ （注意：若因上一次输出有误，或 $A$ 或路径格式错误，本轮输入将为 $-1$。收到 $-1$ 时必须立刻正常结束程序。若第 $Q$ 次问题第一次出错，之后不会再有输入。） 然后你需按照以下格式输出一条路径 $P$，依次给出每步经过的格子坐标 $(x_i, y_i)$： > $x_1\ y_1$ > $x_2\ y_2$ > $\vdots$ > $x_{HW}\ y_{HW}$ 每个 $x_i, y_i$ 必须满足： - $1\leq x_i\leq H,\ 1\leq y_i\leq W$。 - $i\neq j$ 时 $(x_i, y_i)\neq (x_j, y_j)$。 - $|x_i-x_{i+1}|+|y_i-y_{i+1}|=1$，对于 $i=1,2,\ldots,HW-1$。 - $(A_{x_1,y_1}, \ldots, A_{x_{HW},y_{HW}})$ 的逆序对数为 $N$。 ### 注意事项 - **如果收到评测机输入 $-1$，需立刻正常终止程序。若未及时终止则结果不确定。** - **每次输出均需以换行结束并刷新输出流，否则可能会被判定为 TLE。** - **禁止输出多余换行，否则将视为格式错误。** - 子任务全部完成后请立刻结束程序，否则结果不确定。 ### 交互样例 以下为 $H=3,W=4,Q=2$ 的交互示例，仅作说明而不参与正式评测。 | 输入 | 输出 | 说明 | |---|---|---| | 3 4 2 | | $H,W,Q$ 给出。| | | 1101
0110
1010 | 输出 $A$。| | 10 | | 第一次 $N$。| | | 3 2
3 3
3 4
2 4
1 4
1 3
2 3
2 2
1 2
1 1
2 1
3 1 | 输出路径。| | 15 | | 第二次 $N$。| | | 1 1
2 1
3 1
3 2
3 3
3 4
2 4
2 3
2 2
1 2
1 3
1 4 | 输出路径。| # 输入输出样式 ## 输入 无。 ## 输出 无。 # 提示 - $H=4,W=500,Q=200$ - $0\leq N\leq 999900$ - 所有输入均为整数。 由 ChatGPT 5 翻译