AT_ahc033_a.[AHC033A] Container Handling with Cranes

有一个 $N\times N$ 格的集装箱码头。最左上角的格子的坐标为 $(0,0)$，从那里向下走 $i$ 格、向右走 $j$ 格后的位置坐标为 $(i,j)$。编号为 $0$ 到 $N^2-1$ 的 $N^2$ 个集装箱将被运送进来，需要通过操作 $N$ 台起重机，按照指定顺序将它们搬出。

在地图的左端和右端，分别存在如下的搬入口和搬出口：

• 搬入口：左端的每个格子都是搬入口，每个搬入口会依次运送 $N$ 个集装箱。提前知道每个搬入口将运送哪些编号的集装箱，从 $(i,0)$ 搬入口第 $j$ 个被运送进来的集装箱编号为 $A_{i,j}$。
• 搬出口：右端的每个格子都是搬出口，每个搬出口上的集装箱会立即被运出。希望从 $(i,N-1)$ 搬出口依次搬出编号为 $N\times i,N\times i+1,\cdots,N\times i+N-1$ 的集装箱。

每个格子（包括搬入口和搬出口）最多只能放置 $1$ 个集装箱。除了搬出口外，放置的集装箱不会被搬出，因此可以作为调整顺序的临时存放点。

起重机分为 $1$ 台大型起重机和 $N-1$ 台小型起重机两种。初始状态下，大型起重机位于 $(0,0)$，小型起重机分别位于 $(1,0),\ (2,0),\ \cdots,\ (N-1,0)$。

每台起重机可以进行抓取集装箱、放下集装箱、移动到相邻格子等操作。只要目标格子没有集装箱，起重机总是可以移动过去；如果没有抓取集装箱，也可以移动到有集装箱的格子。另一方面，抓取集装箱时能否移动到有集装箱的格子，取决于起重机的类型。

大型起重机可以高高举起集装箱，因此即使抓着集装箱也能移动到有集装箱的格子。小型起重机举起的高度较低，因此抓着集装箱时不能移动到有集装箱的格子。

每回合，每台起重机可以独立选择以下操作之一：

• P：抓取当前位置的集装箱。如果已经抓着集装箱，或当前位置没有集装箱，则判为 WA。
• Q：放下抓着的集装箱，放在当前位置。如果没有抓着集装箱，或当前位置已有集装箱，则判为 WA。
• U、D、L、R：向上、下、左、右相邻格子移动。小型起重机在抓着集装箱时，目标格子不能有集装箱。不能移动到 $N\times N$ 格外。
• .：什么都不做，停留在原地。
• B：爆破起重机。抓着集装箱时不能爆破。被爆破的起重机会从棋盘上移除，之后只能执行 . 操作。

如果进行了禁止的操作，则判为 WA。

无论是否抓着集装箱，起重机之间不能重叠或相互穿越。即，不能有多个起重机在同一格，也不能有两台起重机互换位置。

每台起重机的操作是同时进行的，因此，格子 $p$ 上的起重机移动到 $q$，同时 $q$ 上的起重机移动到 $r$（$r\neq p$）或爆破是允许的。但如果 $r=p$，则属于穿越移动，不允许。

每回合包括以下 $3$ 个步骤：

1. 对于还有集装箱未运送的每个搬入口，如果该格子没有集装箱且没有抓着集装箱的起重机，则下一个集装箱被放置到该格子。
2. 执行每台起重机的操作。
3. 对于每个搬出口，如果该格子有集装箱，则将其搬出并从棋盘上移除。

最多可以重复 $10000$ 回合。请设计操作序列，使得能以较短回合数、尽量按指定顺序将集装箱搬出。

输入通过标准输入给出，格式如下：

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

• 所有测试用例中 $N=5$ 固定。
• $A_{i,j}$ 表示从 $(i,0)$ 搬入口第 $j$ 个被运送进来的集装箱编号，$0\leq A_{i,j}\leq N^2-1$，且所有 $A_{i,j}$ 互不相同。

请按以下格式输出到标准输出：

$S_0$
$\vdots$
$S_{N-1}$

每个 $S_i$ 仅由 P、Q、U、D、L、R、.、B 组成的字符串，第 $t$ 个字符表示初始位置在 $(i,0)$ 的起重机第 $t$ 回合的操作。每个字符串长度必须在 $1$ 到 $10000$ 之间。各字符串长度可以不同，若有不同，则需在较短字符串末尾补充 . 使其与最长字符串等长。

查看示例

得分

定义 $M_0,\ M_1,\ M_2,\ M_3$ 如下：

• $M_0$：输出的操作序列的回合数。
• $M_1$：从正确搬出口搬出的集装箱的逆序数总和。即，对于从 $(i,N-1)$ 搬出口搬出的编号 $b$ 满足 $N\times i\leq b<N\times(i+1)$，按搬出顺序记为 $B_{i,0},\cdots,B_{i,n_i-1}$，则所有满足 $0\leq j<k<n_i$ 且 $B_{i,j}>B_{i,k}$ 的三元组 $(i,j,k)$ 总数为 $M_1$。
• $M_2$：从错误搬出口搬出的集装箱总数。即，从每个搬出口 $(i,N-1)$ 搬出的编号 $b$ 不满足 $N\times i\leq b<N\times(i+1)$ 的数量之和。
• $M_3$：未被搬出的集装箱总数。

则绝对分数为（分数越小越好）：

[
M_0+10^2M_1+104M_2+10^6M_3
]

每个测试用例的相对评分为 $ \mathrm{round}(10^9\times\ \frac{全体参赛者的最小绝对分数}{你的绝对分数}) $，所有测试用例的和为你的得分。

最终排名将在比赛结束后，针对更多输入的系统测试得分决定。无论是暂定测试还是系统测试，若某些测试用例输出非法或超时，则该用例的相对评分为 $0$，且不计入“全体参赛者的最小绝对分数”的计算。系统测试仅对最后一次非 CE 的提交进行，因此请确保最终提交正确。

测试用例数

• 暂定测试：50 个
• 系统测试：2000 个，比赛结束后将公开 seeds.txt (sha256=502228d18e6d0d00f92654ad85f13945fc1d2865f69df352aee061a53ebf3cfa)

相对评分系统说明

无论是暂定测试还是系统测试，只有最后一次非 CE 的提交会计入排行榜。用于计算相对评分的“全体参赛者的最小绝对分数”也只考虑排行榜上的最终提交。

排行榜显示的是相对评分，每次新提交都会重新计算相对评分。而提交列表中显示的分数是所有测试用例的绝对分数之和，不显示相对评分。若想了解非最新提交在当前排行榜下的相对评分，需要重新提交。若输出非法或超时，提交列表中的分数为 $0$，但排行榜会显示正确用例的相对评分之和。

关于执行时间

执行时间会有一定波动。系统测试时由于同时运行大量用例，执行时间比暂定测试略长几个百分点。因此，接近时间限制的提交可能在系统测试中 TLE。建议在程序内自行计时并提前终止，或留出充足的时间余量。

输入生成方式

搬入顺序 $A_{i,j}$ 通过将 $0,1,\cdots,N^2-1$ 随机打乱后，每 $N$ 个分组得到。

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

• 网页版：比本地版性能更高，支持动画显示。
• 本地版：需安装 Rust 语言 编译环境。
  • Windows 版编译好的二进制：如不方便搭建 Rust 环境可使用此版本。

比赛期间禁止分享可视化结果、解法或讨论。请注意遵守规则。

由 ChatGPT 4.1 翻译