AT_ahc070_a [AHC070A] Ward the Village

あなたは日本の山奥にある村の村長で、毎年お盆になると発生する怪異に頭を悩ませていた。 今年は巫女の占いにより、村中で $ 10000 $ 回の怪異が起こることが分かった。 そこで、怪異の起こる場所のできるだけ近くに魔除けのお札を立て、被害を抑えることにした。 占いは怪異の起こる場所と順番を告げるが、猶予はない。 あなたは村外れの社を出て村を巡り、怪異の発生と並行してお札を立てていかねばならない。 お札は、社または直前に立てたお札から神力を受け継いで初めて魔除けの力を持つ。 神力の通り道は巫女の祈祷で $ 3 $ 通りまで開くことができ、どの位置関係に開くかは、社を出る前にあなたが決める。 村が受ける被害をできるだけ小さく抑えてほしい。

村庄被划分为一个 $N\times N$ 的网格。设左上角单元格的坐标为 $(0,0)$，而位于该点向下移动 $i$ 格、向右移动 $j$ 格的单元格坐标为 $(i,j)$。每一回合 $t=0,1,\cdots,N^2-1$，发生灵异事件的单元格的坐标 $(a_t,b_t)$ 会提前给出。 首先，你可以自由选择 $M$ 个对应关系 $(i_0,j_0),\cdots,(i_{M-1},j_{M-1})$，作为神力可以行进的方向。这里，对于每个 $0\leq m

输入通过标准输入给出，格式如下。 > $N$ $M$ $a_0$ $b_0$ $a_1$ $b_1$ $\vdots$ $a_{N^2-1}$ $b_{N^2-1}$ 各数值满足以下约束条件： - $N=100$ - $M=3$ - $0\leq a_t

输出到标准输出，格式如下。 > $i_0$ $j_0$ $i_1$ $j_1$ $\vdots$ $i_{M-1}$ $j_{M-1}$ $m_0$ $m_1$ $\vdots$ $m_{N^2-1}$

## 评分方式 记最终所有 $N^2$ 轮结束后的危险等级为 $D$。你的得分为： \[ \mathrm{round}\left(\frac{10^6\times N^3}{D+1}\right) \] 总共有 150 个测试用例，提交的得分为所有用例得分之和。如果你的输出不合法，或者某一测试用例超时，则本次提交会被判为 WA 或 TLE，并且得分为 0。比赛期间最高分为最终得分，赛后不设额外测试系统。如有多名选手取得同分，则并列排名，与提交先后顺序无关。 ## 输入生成方式 $N=100$ 且 $M=3$ 固定。$(a_0,b_0),\cdots,(a_{N^2-1},b_{N^2-1})$ 为对所有 $N^2$ 个单元格坐标的等概率随机排列。 ## 工具（输入生成和可视化） - [网页版可视化工具](https://img.atcoder.jp/ahc070/f4sYgUzY.html?lang=zh-cn)：功能强大且支持动画演示。 - [本地版工具下载](https://img.atcoder.jp/ahc070/f4sYgUzY.zip)：需安装 [Rust 语言环境](https://www.rust-lang.org/)。若无法编译，请尝试 `rustup update`。 - [Windows 预编译版本](https://img.atcoder.jp/ahc070/f4sYgUzY_windows.zip)：不熟悉 Rust 可使用此版本。 请注意，比赛期间禁止公开可视化结果或讨论思路、算法等内容。 **从本次短赛起，除有限例外外，不允许使用生成式 AI。更多细则请参考 [公告](https://atcoder.jp/posts/short-ahc-llm-rules-en)。** 由 ChatGPT 5 翻译