A - 増減ソート

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 41000000000

問題文

長さ N = 30000 の数列 A が与えられます。A には 1 から N までの整数が 1 回ずつ現れます。ここから、あなたは以下の操作を K 回行います。

  • 整数 i, j, k, l, v (1 ≦ i ≦ j ≦ N, 1 ≦ k ≦ l ≦ N, 0 ≦ v ≦ N - 1) を指定する。A_i, A_{i+1}, ... , A_{j} の値をそれぞれ v 減少させ、 A_k, A_{k+1}, ... , A_{l} の値をそれぞれ v 増加させる。
  • ただし、A のすべての要素は常に 1 以上 N 以下でなければならない。同じ値が複数出現することは許される。
  • また、区間 [i, j] と区間 [k, l] に重複があってはならず、2 つの区間の長さは等しくなければならない。

あなたは、この操作により、A の各要素の値を A_1 = 1, A_2 = 2, ... , A_N = N にできるだけ近づけたいです。 値 |A_1 - 1| + |A_2 - 2| + … + |A_N - N| ができるだけ小さくなるような手順を出力してください。

制約

  • N = 30000
  • 1000 ≦ K ≦ 3000
  • 与えられる A1 から N までの整数のランダムな順列である。

入力

入力は以下の形式で与えられる。

N K
A_1
A_2
:
A_N

出力

K 回の操作を以下の形式で出力せよ。

i_1 j_1 k_1 l_1 v_1
i_2 j_2 k_2 l_2 v_2
:
i_K j_K k_K l_K v_K

ここで、任意の t に対し、i_t≦j_t かつ k_t≦l_t かつ j_t - i_t = l_t - k_t を満たす必要がある。


採点方法

1 つのテストケースに対する点数は、生成された数列を A として 1,000,000,000 - |A_1 - 1| - |A_2 - 2| - … - |A_N - N| 点となる。

テストケースは 41 ケース与えられる。それぞれのテストケースについて、K = 1000, 1050, 1100, …, 2950, 3000 である。すべてのテストケースに対する点数の和が、その提出の得点となる。

なお、1 ケースでも出力が不正であった場合、example_01 以外の点数は全て 0 点となる。

入力例0

10 3
8
9
1
4
6
7
3
2
10
5
  • この入力は制約を満たしません。

出力例0

1 2 7 8 6
7 7 5 5 4
5 5 10 10 5  
  • 初期状態は {8,9,1,4,6,7,3,2,10,5} です。以下次のように変化します。
  • {2,3,1,4,6,7,9,8,10,5}
  • {2,3,1,4,10,7,5,8,10,5}
  • {2,3,1,4,5,7,5,8,10,10}

入力例1

入力ファイル例はこちらから(zip)

採点結果の「example_01」が、こちらのデータとなります。このデータも採点対象となります。 なお、example_01 は K=2000 のデータです。