AT_ahc062_a [AHC062A] King's Tour

AtCoder 王国は $ N \times N $ のグリッド状の区画に区切られており、各区画にはそれぞれ異なる人数の国民が住んでいる。 国王の高橋君は、国民からの好感度を上げるため、縦・横・斜めに隣接する区画を辿りながら、すべての区画を一度ずつ訪問するツアーを計画している。 ツアーは日を追うごとに盛り上がっていくので、後の日に訪れた区画ほど、住人の高橋君への好感度が高くなる。 高橋君が得る好感度の総和がなるべく大きくなるようなツアーを計画してほしい。

$ N \times N $ の区画に区切られた王国がある。左上の区画を $ (0,0) $ とし、下方向に $ i $ 区画、右方向に $ j $ 区画進んだ区画を $ (i,j) $ とする。 区画 $ (i,j) $ には $ A_{i,j} $ 人の国民が住んでいる。 $ 0 $ 日目から $ N^2-1 $ 日目までの $ N^2 $ 日間で、すべての区画をちょうど一度ずつ訪問するツアーを考える。 $ k $ 日目に訪問する区画を $ (i_k, j_k) $ とする。 このとき、連続する 2 日に訪問する区画は、 **縦・横・斜め** に隣接していなければならない。 より厳密には、各 $ k=0,1,\dots,N^2-2 $ について \\\[ \\max\\bigl(|i\_k-i\_{k+1}|,\\ |j\_k-j\_{k+1}|\\bigr)=1 \\\] が成り立つ必要がある。 ツアーの開始区画と終了区画は任意に選んでよい。 ツアーの $ k $ 日目に訪問した区画では、住民 1 人あたり $ k $ の好感度が得られる。 このとき、高橋君が得る好感度の総和は \\\[ \\sum\_{k=0}^{N^2-1} k\\cdot A\_{i\_k, j\_k} \\\] である。 高橋君が得る好感度の総和がなるべく大きくなるような訪問順を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_{0,0} $ $ \cdots $ $ A_{0,N-1} $ $ \vdots $ $ A_{N-1,0} $ $ \cdots $ $ A_{N-1,N-1} $ - すべてのテストケースにおいて、 $ N=200 $ で固定である。 - 区画 $ (i,j) $ の住民数 $ A_{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 $ である。 [例を見る](https://img.atcoder.jp/ahc062/u5OpcTjC.html?lang=ja&seed=0&output=sample)

### 得点 高橋君が得る好感度の総和を $ V $ としたとき、 \\\[ \\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} $ とする。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc062/u5OpcTjC.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc062/u5OpcTjC.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc062/u5OpcTjC_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。