D - Distributed Sorting Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100100

問題文

時は 20XX 年,世界は Distributed AtC◯der 社の支配によるディストピアである.現在,人々の娯楽は分散・並列処理を題材としたプログラミングコンテストに限られている.例えば,週末に家族でスーパーコンピュータを (ssh で) 訪れるというのはとてもよく見られる光景である. (問題文参考: UTPC 2011 問題 A

(実際のところ以下で述べる問題設定は分散というより並列処理で Distributed Sorting というより Parallel Sorting っぽいのだが,頭文字が D の方が都合がいいし,ここで言い訳もしていることだし,とにかく今日はクリスマスなので我々は細かいことは気にしない.)

分散・並列処理においては,基礎的と思える処理でも多種多様な工夫が考えられることが多くある.たとえば,NN 個の相異なる整数からなる整数列 X1X_1, X2X_2, ..., XNX_N を昇順にソートする処理を考えよう.

ソートには,以下の 11 種類の操作が可能なマシンを用いるとする.

  • 操作: 2k2k 個の相異なるインデックス A1A_1, A2A_2, ..., A2kA_{2k} を入力として与えると,各 ii (1ik1 \leq i \leq k) に対し XA2i1X_{A_{2i-1}}XA2iX_{A_{2i}} (XXA2i1A_{2i-1} 番目と A2iA_{2i} 番目) の値を交換する.ただし,各 jj (1j2k1 \leq j \leq 2k) に対し 1AjN1 \leq A_j \leq N でなければならない.

たとえば X=(5,3,1,2,4)X = (5, 3, 1, 2, 4) のとき k=2k=2(A1,A2,A3,A4)=(1,3),(2,4)(A_1, A_2, A_3, A_4) = (1, 3), (2, 4) として操作を行うと,X=(1,2,5,3,4)X = (1, 2, 5, 3, 4) になる.

この操作だけを使って XX を昇順にソートするために必要な操作の最小回数を求め,実際にその最小回数の操作で XX をソートする手順をひとつ出力するようなプログラムを作成せよ.

制約

  • 1N1051 \leq N \leq 10^5
  • 1Xi1091 \leq X_i \leq 10^9
  • XiX_i は相異なる整数.

入力

入力は以下の形式で標準入力から与えられる.

NN
X1X_1 X2X_2 ... XNX_N

出力

11 行目に XX を昇順にソートするために必要な操作の最小回数を出力し,それに続いて,各操作の内容を 11 操作につき 11 行で出力せよ.

操作を表す行の最初には,値の交換を行うペア数 kk を出力せよ.その後,空白に続いて 2k2k 個の整数 A1A_1, A2A_2, ..., A2kA_{2k} を空白区切りで出力せよ.


入力例 1Copy

Copy
3
2 3 1

出力例 1Copy

Copy
2
1 1 3
1 2 3

操作の回数が最小であり,正しく昇順にソートできるような手順であれば,これ以外の出力でも正解と見なされる.たとえばこの入力例に対しては

2
1 1 2
1 3 1

のような出力も正解と見なす.


入力例 2Copy

Copy
3
1 2 3

出力例 2Copy

Copy
0

入力例 3Copy

Copy
5
5 4 3 2 1

出力例 3Copy

Copy
1
2 1 5 2 4


2025-01-05 (Sun)
10:58:31 +00:00