← 返回题目列表

Codeforces · 1012/E

E. 循环排序

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

给你一个 $$$n$$$ 正整数数组 $$$a_1, a_2, \dots, a_n$$$。您可以多次执行以下操作:选择多个不同的索引 $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) 并将 $$$i_1$$$ 位置上的数字移动到 $$$i_2$$$ 位置,将 $$$i_2$$$ 位置上的数字移动到 $$$i_3$$$ 位置,...,将该位置上的数字移动$$$i_k$$$ 到位置 $$$i_1$$$。换句话说,该操作循环移位元素:$$$i_1 \to i_2 \to \ldots i_k \to i_1$$$。

例如,如果您有 $$$n=4$$$,数组 $$$a_1=10、a_2=20、a_3=30、a_4=40$$$,并且您选择三个索引 $$$i_1=2$$$、$$$i_2=1$$$、$$$i_3=4$$$,则生成的数组将变为$$$a_1=20,a_2=40,a_3=30,a_4=10$$$。

你的目标是用最少的操作次数使数组按非降序排序。附加约束是所有操作的循环长度总和应小于或等于数字 $$$s$$$。如果在满足该约束的同时无法对数组进行排序,您的解决方案也应该报告这一点。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq s \leq 200\,000$$$) - 数组中的元素数量以及循环长度总和的上限。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ — 数组的元素 ($$$1 \leq a_i \leq 10^9$$$)。

输出

如果无法使用总长度不超过 $$$s$$$ 的循环对数组进行排序,请打印单个数字“-1”(为了清楚起见,使用引号)。

否则,打印单个数字 $$$q$$$ — 对数组进行排序所需的最少操作数。

在接下来的 $$$2 \cdot q$$$ 行中,按照应用于数组的顺序打印操作描述。第 $$$i$$$ 操作的描述从一行开始,其中包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$)——循环的长度(即所选索引的数量)。下一行应包含 $$$k$$$ 不同的整数 $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) — 循环的索引。

这些循环的长度总和应小于或等于 $$$s$$$,并且在应用这些 $$$q$$$ 操作后应对数组进行排序。

如果有多个可能的答案且最优 $$$q$$$,请打印其中任何一个。

示例

输入 #1

5 5
3 2 3 1 1

输出 #1

1
5
1 4 2 3 5

输入 #2

4 3
2 1 4 3

输出 #2

-1

输入 #3

2 0
2 2

输出 #3

0

注意

在第一个示例中,还可以使用总长度为 5 的两个操作对数组进行排序:首先应用循环 $$$1 \to 4 \to 1$$$ (长度为 2),然后应用循环 $$$2 \to 3 \to 5 \to 2$$$ (长度为 3)。但是,这将是错误的答案,因为您被要求使用尽可能少的操作数,在这种情况下为 1。

在第二个示例中,可以使用总长度为 4 的两个循环($$$1 \to 2 \to 1$$$ 和 $$$3 \to 4 \to 3$$$)对数组进行排序。然而,使用更短的周期是不可能实现相同的目的,而这是 $$$s=3$$$ 所要求的。

在第三个示例中,数组已经排序,因此不需要任何操作。空循环集的总长度被认为为零。