AT_ahc062_a.[AHC062A] King's Tour

有一个王国被划分为 $N \times N$ 的区域网格。左上角的区域被标记为 $(0,0)$，向下移动 $i$ 个区域、向右移动 $j$ 个区域所到达的区域为 $(i,j)$。区域 $(i,j)$ 有 $A_{i,j}$ 名居民。

现在考虑一条旅行路线，在 $N^2$ 天内恰好访问每个区域一次，从第 $0$ 天到第 $N^2-1$ 天。第 $k$ 天访问的区域为 $(i_k, j_k)$。

要求连续两天所访问的区域必须为相邻区域，允许上下、左右或对角线相邻。更精确地说，对于每个 $k=0,1,\dots,N^2-2$，需要满足

[
\max\bigl(|i_k-i_{k+1}|,~ |j_k-j_{k+1}|\bigr)=1
]

起点和终点可以任取。

第 $k$ 天到达的区域，每名居民会贡献 $k$ 点好感。Takahashi 获得的总好感值为

[
\sum_{k=0}^{N2-1} k\cdot A_{i_k, j_k}
]

请你找出一条访问顺序，使 Takahashi 获得的总好感值尽可能大。

输入以如下格式从标准输入给出：

$N$
$A_{0,0}$ $A_{0,1}$ $\cdots$ $A_{0,N-1}$
$\vdots$
$A_{N-1,0}$ $A_{N-1,1}$ $\cdots$ $A_{N-1,N-1}$

• 所有测试用例中 $N=200$。
• $A_{i,j}$（区域 $(i,j)$ 的居民数）是满足 $1\leq A_{i,j}\leq N^2$ 的整数。

令第 $k$ 天访问的区域为 $(i_k, j_k)$。请输出如下格式到标准输出：

$i_0$ $j_0$
$\vdots$
$i_{N^2-1}$ $j_{N^2-1}$

你的输出必须满足以下所有条件：

• 对每个 $k=0,1,\cdots,N^2-1$，$i_k$ 和 $j_k$ 是 $0$ 到 $N-1$ 之间的整数（含端点）。
• 所有 $(i_k, j_k)$ 在 $k=0,1,\cdots,N^2-1$ 时均不相同。
• 对每个 $k=0,1,\cdots,N^2-2$，都有 $ \max(|i_k-i_{k+1}|,\ |j_k-j_{k+1}|)=1 $。

评分方式

设 $V$ 为 Takahashi 获得的总好感值，则该测试点的分数为

[
\mathrm{round}\left(\frac{V}{N^2}\right)
]

共有 $100$ 个测试点，提交的总分为各测试点得分之和。如果输出非法或部分测试点超时，该提交整体将按 WA 或 TLE 判定，分数为零。比赛期间获得的最高分即为最终排名，赛后不会再有系统测试。如果多名参赛者得分相同，则排名相同，与提交时间无关。

输入生成方式

• 所有测试点均有 $N=200$。
• $1$ 到 $N^2$ 的整数被均匀随机洗牌，依次赋给 $A_{0,0}, A_{0,1},\cdots,A_{0,N-1}, A_{1,0},\cdots,A_{N-1,N-1}$。

工具（输入生成器和可视化工具）

• 网页版：比本地版更强大，支持动画。
• 本地版：需要配置 Rust 语言 环境。
  • Windows 预编译版：如果不熟悉 Rust 环境可优先考虑。

请注意，比赛期间禁止共享可视化结果、讨论解法或思路。

由 ChatGPT 5 翻译