AT_ahc064_a [AHC064A] Non-Crossing Railcar Rearrangement

AtCoder国の高橋鉄道から、あなたに緊急の依頼が届いた。翌朝の一斉出発に向けて、貨物ターミナルでの車両の並べ替えを手伝ってほしいというのだ。 貨物ターミナルには、列車が出発するための線路（出発線）が複数並んでおり、車両が配置されている。 また、各出発線の末尾側には、車両を一時的に移しておくための線路（待避線）が同数設けられている。 出発線と待避線の間で車両を適切に移動させることで、各出発線に車両を所定の順序で並べたい。  ただし、複数の移動を同時に行う際、出発線と待避線を結ぶ経路どうしが交差すると、車両同士が互いの進路を塞いでしまう。そのため、同じタイミングに行う移動は、経路が互いに交差しないように選ぶ必要がある。 高橋鉄道のために、できるだけ少ない手順で、全ての車両を所定の順序に並べてほしい。

在货运站中有 $R$ 条发车轨道，另有 $R$ 条侧线轨道位于发车轨道出口方向的对面。发车轨道与侧线轨道编号均为 $0,1,\ldots,R-1$，从左到右依次编号。下面我们将发车轨道出口一端称为“前端”，另一端称为“后端”；对于侧线轨道，靠近发车轨道的一端称为“前端”，另一端称为“后端”。 每条发车轨道通过铁轨与每条侧线轨道相连，轨道车可以在发车轨道与侧线轨道之间移动。每条发车轨道最多可容纳 15 节轨道车，每条侧线轨道最多可容纳 20 节轨道车。若某次移动会导致超出容量，则该移动无效。 初始时，每条发车轨道上都有 10 节轨道车。每节轨道车分配有唯一的编号 $0,\ldots,10R-1$，编号为 $Y_{r,c}$ 的轨道车位于第 $r$ 条发车轨道从前端算起的第 $c$ 个位置上。所有侧线轨道最初为空。通过在发车轨道和侧线轨道之间移动轨道车，目标是使每条发车轨道 $r$ 上的轨道车从前端起的顺序依次为编号 $10r, 10r+1, \ldots, 10r+9$。 每一回合，你可以**同时执行多次移动**，共有如下两类操作。每次操作涉及 $k$ 节连续的轨道车（$k \ge 1$），且其顺序保持不变。 - （type = 0）从第 $i$ 条发车轨道的后端取出 $k$ 节连续轨道车，并将它们接到第 $j$ 条侧线轨道的前端。 - （type = 1）从第 $j$ 条侧线轨道的前端取出 $k$ 节连续轨道车，并将它们接到第 $i$ 条发车轨道的后端。  为确保列车安全，每回合内选定的所有移动线路必须互不相交（不论方向），即需满足以下两个条件： - 同一条发车轨道或侧线轨道在同一回合内不能被使用超过一次。 - 若在同一回合中同时执行了发车轨道 $i_1$ 与侧线轨道 $j_1$ 之间的移动和发车轨道 $i_2$ 与侧线轨道 $j_2$ 之间的移动，则若 $i_1 < i_2$，必须有 $j_1 < j_2$。 你最多可以进行 4000 个回合的移动。

输入通过标准输入给出，格式如下： > $R$    $Y_{0,0}$    $\cdots$    $Y_{0,9}$    $\vdots$    $Y_{R-1,0}$    $\cdots$    $Y_{R-1,9}$ - 在每个测试用例中，$R=10$。 - $Y_{r,c}$ 表示初始状态下，第 $r$ 条发车轨道从前端开始第 $c$ 个位置上的轨道车编号（$0 \leq c < 10$）。 - $Y_{r,c}$ 在所有输入中恰好覆盖了 $0,\ldots,10R-1$。

请按如下格式输出你的移动操作序列： > $T$   $K_0$    $\mathrm{type}$   $i$   $j$   $k$    $\vdots$    $\mathrm{type}$   $i$   $j$   $k$    $\vdots$   $K_{T-1}$    $\mathrm{type}$   $i$   $j$   $k$    $\vdots$    $\mathrm{type}$   $i$   $j$   $k$ 其中，$T$ 表示你执行的回合数（$T \leq 4000$）。在输出 $T$ 后，对于每一回合 $t=0,1,\cdots,T-1$，依次输出如下内容： - 首先单独一行输出该回合的操作数 $K_t$（$1 \leq K_t \leq R$）。 - 随后 $K_t$ 行，每行输出一次操作，格式为 `type i j k`（$type \in \{0,1\}$，$0 \leq i,j < R$，$k \geq 1$）。 - 当 $type=0$ 时，表示从第 $i$ 条发车轨道的后端取出 $k$ 节轨道车，并将其接到第 $j$ 条侧线轨道的前端。 - 当 $type=1$ 时，表示从第 $j$ 条侧线轨道的前端取出 $k$ 节轨道车，并将其接到第 $i$ 条发车轨道的后端。

### 评分方式 设输出移动序列的回合数为 $T$。 若所有发车轨道最终完全达到目标排列，则得分为 $100R + 4000 - T$。 否则，最终每节仍位于发车轨道上的轨道车（至多 $10R$ 节）按照以下方式计分： - 若该轨道车被放在了正确的发车轨道上，得 1 分； - 若其在发车轨道上从前端起的位置也完全正确，再额外加 9 分。 若回合数超过 4000，或者输出违反了不交叉约束或任意轨道容量约束，则本次提交判为 WA。 共有 $150$ 个测试用例，最终得分为每个测试用例分数总和。若你的输出格式非法或时间耗时过长，则本次提交整体记为 WA 或 TLE，得分为零。最终排名以比赛期间的最高分为准，赛后不再有系统测试。分数相同者排名并列，并不考虑提交时间。 ### 输入生成方式 每个测试用例均有 $R=10$。 首先生成 $0,1,\ldots,10R-1$ 构成的整数序列的一个随机排列，然后按顺序赋值给 $Y_{0,0}, Y_{0,1}, \ldots, Y_{0,9}, Y_{1,0}, \ldots, Y_{R-1,9}$。 ### 工具（输入生成器和可视化工具） - [网页版](https://img.atcoder.jp/ahc064/fLqO0Ras.html?lang=zh)：比本地版更强大，使用动画展示过程。 - [本地版](https://img.atcoder.jp/ahc064/fLqO0Ras.zip)：需要 [Rust 语言](https://www.rust-lang.org/)环境。 - [Windows 版预编译包](https://img.atcoder.jp/ahc064/fLqO0Ras_windows.zip)：如果不了解 Rust 环境，可直接使用。 请注意，比赛期间禁止分享可视化结果或讨论题解、思路。 由 ChatGPT 5 翻译