AT_toyota2023summer_final_a Transit Warehouse

[problemUrl]: https://atcoder.jp/contests/toyota2023summer-final-open/tasks/toyota2023summer_final_a $ D\times\ D $ マスの倉庫がある。 一番北西のマスの座標を $ (0,0) $ とし、そこから南方向に $ i $ マス、東方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 $ D $ は奇数であり、$ (0,(D-1)/2) $ のマスに倉庫の出入り口がある。 出入り口とその隣接する $ 3 $ マスを除いた $ D^2-4 $ マスのうち、$ N $ マスに通行不能な障害物が置かれている。 $ D^2-1-N $ 個のコンテナが一つずつに運び込まれて来る。 各コンテナには $ 0 $ から $ D^2-2-N $ の固有の番号が振られており、各番号はそのコンテナを運び出したい順序を示している。 **コンテナが運び込まれて来る順番の情報は事前には与えられず、運び込まれて来たタイミングでそのコンテナに振られている番号が明らかになる。** 出入り口と障害物マス以外の $ D\times\ D-1-N $ マスにはそれぞれ高々 $ 1 $ つのコンテナを格納することが出来る。 コンテナが1つ運び込まれて来る度に、そのコンテナを格納する場所を選択せよ。 格納先は以下の条件を満たす必要がある。 1. 出入り口と障害物マス以外であり、かつ既にその場所に他のコンテナが格納されていない。 2. 出入り口のマスから、4方向に隣接する空きマスのみを経由して格納先のマスに到達可能である。 コンテナの格納が全て完了した後、全てのコンテナを任意の順番で1つずつ運び出す。 運び出すコンテナは以下の条件を満たす必要がある。 1. 出入り口のマスから、4方向に隣接する空きマスのみを経由して運び出すコンテナが格納されているマスに到達可能である。 出来るだけ指定された順序で運び出すことが出来るように、コンテナの格納先と運び出す順序を最適化せよ。 ### Input & Output Format まずはじめに、標準入力から倉庫の大きさ $ 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 $ を満たす。 各障害物 $ (ri_k,rj_k) $ の座標は出入り口とその隣接する3マスのいずれとも異なり、更に障害物以外の全てのマスは出入り口のマスから到達可能であることが保証されている。 上記の情報を読み込んだら、以下の処理を $ D^2-1-N $ 回繰り返す。 $ d(0\leq\ d\leq\ D^2-2-N) $ 回目の処理ではまず、標準入力から $ d $ 番目に運び込まれて来たコンテナの番号 $ t_d $ が一行で与えられる。 各 $ t_d $ は $ 0 $ 以上 $ D^2-2-N $ 以下の整数値であり、各コンテナの番号は一意である。 $ t_d $ の情報を読み込んだら、そのコンテナを格納する先のマスの座標 $ (pi_d,pj_d) $ を以下の形式で一行で標準出力に出力せよ。 > $ pi_d $ $ pj_d $ **出力の後には改行をし、更に標準出力を flush しなければならない。** そうしない場合、TLEとなる可能性がある。 **$ d $ 回目の出力するまで、$ d+1 $ 個目のコンテナに関する入力は与えられないので注意せよ。** 全てのコンテナの格納が完了後、コンテナを運び出す順序を決定せよ。 $ k $ 番目に運び出すコンテナの座標を $ (qi_k,\ qj_k) $ としたとき、以下の形式で標準出力に出力せよ。 > $ qi_0 $ $ qj_0 $ $ qi_1 $ $ qj_1 $ $ \vdots $ $ qi_{D^2-2-N} $ $ qj_{D^2-2-N} $ 解答プログラムは、# から始まるコメント行を出力に含めても良い。 Web版ビジュアライザを使用すると、コメント行を対応するタイミングで表示出来るため、デバッグや考察等に役立てることが出来る。 ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能である。 #### 例 $ d $ Input Output 事前情報 ``` 9 0 ``` 0 ``` 16 ``` ``` 8 0 ``` 1 ``` 13 ``` ``` 8 8 ``` $ \vdots $ 79 ``` 34 ``` ``` 0 5 ``` 運び出す順序 > 0 3 0 5 0 2 $ \vdots $ 8 8 [例を見る](https://img.atcoder.jp/toyota2023summer-final/TqK1K6OG.html?lang=ja&seed=0&output=sample)

N/A

N/A

### ストーリー 高橋くんはコンテナを輸送する中継倉庫の管理をしている。 この倉庫には本日いくつかのコンテナが運び込まれる予定で、運び込まれた全てのコンテナは翌日決められた順序でトラックに積まれて運び出される。 各コンテナが到着する順番は不明であり、運び出す順序を考慮して臨機応変に倉庫内の適切な場所に格納して欲しい。 ### 得点 $ 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言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。