← 返回题目列表

AtCoder · future2018career_a

A. 增加/减少排序

中文机器翻译题面 查看原题

配点 : 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
  • 给出 它是 A 是 您也可以写 1 减去 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 数据。