AT_toyota2023summer_final_a Transit Warehouse
题目描述
仓库是一个 $D \times D$ 的网格，最西北角的坐标为 $(0, 0)$。如果从该点向南走 $i$ 格、向东走 $j$ 格，格子坐标为 $(i, j)$。注意，$D$ 是奇数，仓库的出入口位于 $(0, (D-1)/2)$。除去出入口及其相邻的三个格子，仓库中 $D^2-4$ 个格子中有 $N$ 个被障碍物占据。
仓库需要容纳 $D^2 - 1 - N$ 个集装箱，每个集装箱有一个唯一编号，该编号为 $0$ 至 $D^2 - 2 - N$ 之间的整数，也代表期望运出的顺序。由于集装箱的编号只有在运到仓库时才能得知，因此需要根据编号决定其存储位置。存放位置需满足以下条件：
1. 不能是进出口或障碍物所在的格子，且该位置必须是空的。
2. 必须可以从进出口通过空闲的相邻格子（上下左右四个方向）到达。
一旦所有集装箱都被成功存入仓库，就需要按顺序运出。每次运出时，必须满足同样的路径要求，即：
1. 需要从进出口通过空闲的相邻格子到达所要运出集装箱的格子。
请尽可能根据指定顺序优化位置存放和运出计划。
### 输入格式
程序首先从标准输入读取仓库大小 $D$、障碍物数量 $N$，以及每个障碍物的坐标 $(ri_0, rj_0), \cdots, (ri_{N-1}, rj_{N-1})$。格式如下：
> $D$ $N$ $ri_0$ $rj_0$ $\vdots$ $ri_{N-1}$ $rj_{N-1}$
所有测试用例中，$D$ 都固定为 $9$。$N$ 的范围为 $0 \leq N \leq D$，每个障碍物的坐标与进出口及其相邻的3个格子不同，且除去障碍物位置外，其他所有位置都可以从入口通过相邻格子到达。
获取以上信息后，程序接下来需要处理 $D^2 - 1 - N$ 次操作。
对于第 $d$ 次操作，从标准输入读取第 $d$ 个被送入的集装箱的编号 $t_d$：
> $t_d$
此时应立即输出这个集装箱的存储位置坐标 $(pi_d, pj_d)$：
> $pi_d$ $pj_d$
**输出后必须换行并刷新标准输出，否则有可能导致超时（TLE）错误。注意，在未完成第 $d$ 次输出之前，不会提供第 $d+1$ 个集装箱的信息。**
在完成所有集装箱的存储后，决定运出顺序。设运出集装箱的坐标顺序为 $(qi_0, qj_0), (qi_1, qj_1), \cdots, (qi_{D^2-2-N}, qj_{D^2-2-N})$，输出格式为：
> $qi_0$ $qj_0$ $qi_1$ $qj_1$ $\vdots$ $qi_{D^2-2-N}$ $qj_{D^2-2-N}$
程序可以输出以 `#` 开头的注释行，在 Web 可视化工具中可以动态显示这些注释以方便调试和分析。评测程序会忽略所有注释行，因此可以提交包含注释的程序。
### 数据范围与提示
### 得分
考虑已运出的每个集装箱，其编号为 $b_i\ (0 \leq b_i \leq D^2 - 2 - N)$。定义 $B$ 为序列 $b_0, b_1, ..., b_{D^2 - 2 - N}$ 中的逆序对数，即所有满足 $i < j$ 且 $b_i > b_j$ 的序对 $(i, j)$ 的总数。得分计算公式如下：
\[ \mathrm{round}\left(10^9 \times \frac{(D^2 - N)(D^2 - 1 - N) / 2 - B}{(D^2 - N)(D^2 - 1 - N) / 2}\right) \]
每个 $N=0, 1, ..., 9$ 都有 30 个测试用例，总计 300 个测试用例。每个测试用例得分累加后为最终提交得分。如果任何一个测试用例输出不正确或超时，整���提交会被判定为错误（WA 或 TLE）。比赛期间取得的最高分将用于最终排名，竞赛结束后不进行系统测试。得分相同的参赛者将并列排名。
### 输入生成方法
障碍物数量 $N$ 是从 $0$ 到 $D$ 的整数中随机选取。每个障碍物的坐标都是从剩余空格中随机选取 $N$ 个不同的格子，确保所有非障碍物位置可从入口相通。集装箱编号 $t_0, t_1, ..., t_{D^2-2-N}$ 是通过对 $0, 1, ..., D^2-2-N$ 的随机排列生成的。
### 工具（输入生成器与可视化工具）
- [Web版](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.html?lang=ja)：性能更好，可动画显示并支持手动操作。
- [本地版](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.zip)：需要安装[Rust语言](https://www.rust-lang.org/ja)编译环境。
- [Windows预编译版本](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG_windows.zip)：如果不想安装Rust环境，可以使用此版本。
请注意，比赛期间禁止共享可视化结果或讨论解法和策略。
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无
说明/提示
### ストーリー
高橋くんはコンテナを輸送する中継倉庫の管理をしている。 この倉庫には本日いくつかのコンテナが運び込まれる予定で、運び込まれた全てのコンテナは翌日決められた順序でトラックに積まれて運び出される。 各コンテナが到着する順番は不明であり、運び出す順序を考慮して臨機応変に倉庫内の適切な場所に格納して欲しい。
### 得点
$ i\ (0\leq\ i\leq\ D^2-2-N) $ 番目に運び出したコンテナの番号を $ b_i\ (0\leq\ b_i\leq\ D^2-2-N) $ とする。 $ B $ を $ b_0,\cdots,b_{D^2-2-N} $ の転倒数、すなわち、$ i\ \ b_j $ であるようなペア $ (i,j) $ の総数とする。 このとき、以下の得点が得られる。
\\\[ \\mathrm{round}\\left(10^9\\times \\frac{(D^2-N)(D^2-1-N)/2-B}{(D^2-N)(D^2-1-N)/2}\\right) \\\]
各 $ N=0,1,\cdots,9 $ に対して $ 30 $ 個ずつ、合計で 300 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
### 入力生成方法
障害物の個数 $ N $ は $ 0 $ 以上 $ D $ 以下の整数から一様ランダムに生成される。 各障害物の座標は、出入り口とその隣接マス以外の中から異なる $ N $ 個がランダムに生成され、残りのマスのうちで到達不能なものがある場合は障害物の座標の生成をやり直す。 コンテナの番号 $ t_0,\cdots,t_{D^2-2-N} $ は $ 0,1,\cdots,D^2-2-N $ をランダムな順に並び替えることで生成される。
### ツール(入力ジェネレータ・ビジュアライザ)
- [Web版](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。
- [ローカル版](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。
- [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。