AT_ahc068_a [AHC068A] Rectangle Swap

有一个 $N \times N$ 的网格。左上角单元格的坐标为 $(0,0)$。从该格向下 $i$ 格、向右 $j$ 格的位置坐标为 $(i,j)$。 网格的外边界被墙包围，相邻单元格间也可能存在墙。保证任意两个格子之间都可以通过不跨越墙，依次向上、下、左、右移动经过相邻格子到达。 一个以左上角单元格为 $(r,c)$，高为 $h>0$，宽为 $w>0$ 的矩形用 $(r,c,h,w)$ 表示，定义为以下格子集合： \[ \{(r+x,c+y) \mid 0 \leq x < h,\ 0 \leq y < w\} \] 每个格子中恰好有一张编号为 $0,1,\dots,N^2-1$ 的卡牌。给定卡牌的初始排列，反复进行如下操作，最终将每个格子 $(i,j)$ 中的卡牌变为 $iN+j$ 标号的卡牌。 每次操作如下： 首先选择竖直或水平方向中的一种，并选定一个矩形 $R=(r,c,h,w)$，需满足下列条件： - 若选择竖直方向，高 $h$ 必须为偶数。 - 若选择水平方向，宽 $w$ 必须为偶数。 - $R$ 内所有单元格均在网格范围内。 - $R$ 内没有任何一对相邻格子间有墙。 然后，对所选的矩形区域内的卡牌进行如下交换操作： - 若选择竖直方向，对所有满足 $0\leq x

输入从标准输入读入，格式如下： > $N$ $a_{0,0}$ $\cdots$ $a_{0,N-1}$ $\vdots$ $a_{N-1,0}$ $\cdots$ $a_{N-1,N-1}$ $V_0$ $\vdots$ $V_{N-1}$ $H_0$ $\vdots$ $H_{N-2}$ - 网格规模 $N$ 在所有测试用例中都固定为 $20$。 - $a_{i,j}$ 表示初始时格子 $(i,j)$ 上的卡牌编号。 - $a_{i,j}$ 构成 $0,1,\dots,N^2-1$ 的一个排列。 - 至少存在一个 $(i,j)$ 满足 $a_{i,j} \neq iN+j$。 - 每个 $V_i$ 是长度 $N-1$ 的“0”/“1”串，第 $j$ 个字符为 “1” 表示 $(i,j)$ 和 $(i,j+1)$ 之间有墙，为 “0” 则无墙。 - 每个 $H_i$ 是长度 $N$ 的“0”/“1”串，第 $j$ 个字符为 “1” 表示 $(i,j)$ 和 $(i+1,j)$ 之间有墙，为 “0” 则无墙。 - 任意两个格子之间都可以通过不断移动到无墙的相邻格子到达。

设 $T\ (0\leq T\leq 10^5)$ 为操作次数。第 $t$ 次操作选择的方向用一个字母表示：`V` 表示竖直，`H` 表示水平。第 $t$ 次操作所选择的矩形为 $R_t=(r_t,c_t,h_t,w_t)$。 按如下格式输出每一次操作： > $d_0$ $r_0$ $c_0$ $h_0$ $w_0$ $\vdots$ $d_{T-1}$ $r_{T-1}$ $c_{T-1}$ $h_{T-1}$ $w_{T-1}$

### 评分方式 设你输出的操作数为 $T$。所有操作执行完后，不在目标位置的格子数为 $E$。 得分方式如下： - 若 $E=0$，则得分为 $N^2 + \mathrm{round}\left(10^6 \times \log_2 \frac{10^5}{T}\right)$。 - 若 $E>0$，则得分为 $N^2-E$。 共计 $150$ 个测试用例，最终得分为各测试用例得分之和。如果你的输出不合法或超时则该提交整体判为 WA 或 TLE，得分为零。比赛期间最高分为最终排名依据，比赛结束后不进行系统测试。若多名选手得分相同，则并列排名，提交时间不影响结果。 ### 输入生成 令 $N=20$。 $\mathrm{rand}(L,U)$ 为在 $[L,U]$ 区间均匀随机生成的整数。 #### 墙体生成 单元格的一个角称为“顶点”。 生成 $W = \mathrm{rand}(0,N-1)$。起初格子间没有墙，只有外边界有墙。重复执行以下过程 $W$ 次： 从未与任何墙接触的顶点中随机选择一个，在四个方向中随机挑选一个方向，从该顶点向该方向延伸墙，直到遇到外边界或已存在的墙为止。 #### 初始牌面生成 初始牌面为 $0,1,\dots,N^2-1$ 的随机排列。如果排列已经满足 $a_{i,j}=iN+j$，则重新生成。 ### 工具（输入生成器与可视化器） - [网页版](https://img.atcoder.jp/ahc068/FCpa2O61.html?lang=zh-cn)：支持动画演示，功能优于本地版。 - [本地版](https://img.atcoder.jp/ahc068/FCpa2O61.zip)：需具备 [Rust 语言](https://www.rust-lang.org/)编译环境。 - [Windows 预编译版](https://img.atcoder.jp/ahc068/FCpa2O61_windows.zip)：不熟悉 Rust 环境可用。 比赛期间禁止分享可视化结果或讨论解题思路。 ### 关于生成式 AI 的使用 根据当前 [AtCoder Heuristic Contest 生成式 AI 使用规则—20250616 版](https://info.atcoder.jp/entry/ahc-llm-rules-en)，不允许让 AI 代理自动执行解答程序并基于运行结果自动改进。 不过，最新生成式 AI 系统中，对话服务如 ChatGPT 与 AI 代理如 Codex 的界限日益模糊。即使是对话 AI，也可能在无用户明确指令下自动生成测试用例，运行程序，并根据结果自动进行改进。 部分参赛者已主动要求生成式 AI 不自动改进。为确保公平，任何在本场比赛中使用生成式 AI 的选手需在每次对话开头或通过相关工具自动加载的自定义指令、项目指令、指令文件（如 `AGENTS.md` 或 `CLAUDE.md`）中补充如下声明： ``` 我正在参加 AtCoder Heuristic Contest，将使用本生成式 AI 协助开发解题方案。 使用本 AI 时，适用《AtCoder Heuristic Contest 生成式 AI 使用规则—20250616 版》。 尤其重要的是，除非用户明确发出指令，否则不得在运行方案程序后据此改进方案、思路或代码。 你可以运行方案程序并报告其执行结果、日志、分数等。但报告后必须等待用户新的明确指令后才能基于结果作出改进。 此处“方案程序”指为解答本题创建或正在创建的任何程序，无论是否由用户或 AI 创作，也不论是否已经完工。 ``` 由 ChatGPT 5 翻译