I - そーっとソート
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
(1,\ 2,\ …,\ N) の順列として、数列 a_1,\ a_2,\ …,\ a_N が与えられます。
あなたは、以下の操作を 100,000 回まで行うことができます。
- a_i と a_j の値を入れ替える。ただし、|i-j| = a_i または |i-j| = a_j を満たしていなければならない。
数列を 1,\ 2,\ …,\ N へと並び変えることが出来るか判定し、また、出来るならばその手順を 1 つ示してください。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 … a_N
- 1 行目には数列の要素数 N(1 \leq N \leq 50) が与えられる。
- 2 行目には、数列の要素 a_i が空白区切りで与えられる。
- a_1,\ a_2,\ ,…,\ a_N は (1,\ 2,\ …,\ N) の順列である。
出力
出力は標準出力に行い、末尾に改行を入れること。
もしどのような手順でも 100,000 回以内の操作では数列がソート出来ないならば、MuriyarokonnNaN
と出力すること。
ソートすることが出来る場合は、以下の形式に従い出力すること。
R X_1 Y_1 X_2 Y_2 : X_R Y_R
- 1 行目には操作の回数 R(0 \leq R \leq 100,000) を出力する。
- 2 行目から R 行には操作の詳細を出力する。このうち i 行目には整数 X_i(1 \leq X_i \leq N),\ Y_i(1 \leq Y_i \leq N) を空白区切りで出力する。これは、i 回目の操作では a_{X_i} と a_{Y_i} の値を入れ替えることを表す。(修正,15:41)
入力例1
5 4 2 3 1 5
出力例1
(13:55)1行目の値に誤りがあり、修正しました。
3 2 4 1 2 2 4