#2818. 「eJOI2018」循环排序

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: hiuseues2

题目描述

本题译自 eJOI2018 Problem F. Cycle Sort

给定一个长为 n 的数列 \{a_i\} ,你可以多次进行如下操作:
选定 k 个不同的下标 i_1, i_2, \cdots, i_k (其中 1 \le i_j \le n ),然后将 a_{i_1} 移动到下标 i_2 处,将 a_{i_2} 移动到下标 i_3 处,……,将 a_{i_{k-1}} 移动到下标 i_{k} 处,将 a_{i_k} 移动到下标 i_1 处。

换言之,你可以按照如下的顺序轮换元素: i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_{k-1} \rightarrow i_k \rightarrow i_1

例如: n=4, \{a_i\}=\{ 10, 20, 30, 40\}, i_1=2, i_2=3, i_3=4 ,则操作完成后的 a 数列变为 \{ 10, 40, 20, 30\}

你的任务是用操作次数最少的方法将整个数列排序成不降的。注意,所有操作中选定下标的个数总和不得超过 s 。如果不存在这样的方法(无解),输出 \texttt{-1}

输入格式

第一行, 2 个整数, n s\ (1 \le n \le 2 \times 10^5, 0 \le s \le 2 \times 10^5)
第二行, n 个整数 a_1, a_2, a_3, \cdots a_n ,表示数列 \{a_i\} ,其中 1 \le a_i \le 10^9

输出格式

如果无解,仅输出 \texttt{-1}
否则,第一行输出一个整数 q (可以为 0 ,参见样例 3 ),表示最少需要进行的操作次数。
接下来 2 \times q 行描述每次操作。
对于每次操作,先输出一个整数 k 表示此操作选定的下标数量,然后在下一行中输出 k 个整数 i_1, i_2, \cdots, i_k
在操作次数 q 最少的情况下,你可以输出任意一种可行方案。

样例

样例输入 1

5 5
3 2 3 1 1

样例输出 1

1
5
1 4 2 3 5

样例解释 1

你可以用两次操作 1 \rightarrow 4 \rightarrow 1 2 \rightarrow 3 \rightarrow 5 \rightarrow 2 排序数组,但这样会 WA,因为你的任务是最小化 q ,而最优解的 q=1
一种可行的方法是 1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 1 ,即样例输出。

样例输入 2

4 3
2 1 4 3

样例输出 2

-1

样例解释 2

所有操作中选定下标的个数总和的最小值为 4 (一种可行的方法是 1 \rightarrow 2 \rightarrow 1 3 \rightarrow 4 \rightarrow 3 ),因此无解。

样例输入 3

2 0
2 2

样例输出 3

0

样例解释 3

数组已经有序,因此不需要进行操作。

样例输入 4

6 9
6 5 4 3 2 1

样例输出 4

2
6
1 6 2 5 3 4
3
3 2 1

样例输入 5

6 8
6 5 4 3 2 1

样例输出 5

3
2
3 4
4
1 6 2 5
2
2 1

补充说明

样例 4 和 5 满足子任务 6 和 7 的限制。

数据范围与提示

数据限制

子任务编号 分数 限制
1 0 样例
2 5 n, s \le 2 1 \le a_i \le 2
3 5 n \le 5
4 5 1 \le a_i \le 2
5 10 \{a_i\} 1 n 的所有正整数出现且恰好只出现一次, s=2 \times n
6 10 \{a_i\} 1 n 的所有正整数出现且恰好只出现一次, n \le 1000
7 15 \{a_i\} 1 n 的所有正整数出现且恰好只出现一次
8 15 s=2 \times n
9 15 n \le 1000
10 20 无特殊限制