logo AlgoBeat OnlineJudge
登录 注册

#214355. [COI 2011] 排序 / SORT

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

译自 COI 2011 T1


为了将工厂中的工作自动化,Mirko 希望利用一台老旧的分拣机器人来整理箱子。工厂中有 个箱子,编号分别为 的不同整数,需要按照编号升序排列。

这台分拣机器人只能执行一种特定操作:对于给定的一组不同位置,机器人会循环移动这些位置上的箱子。例如,如果初始箱子顺序为 ,而 Mirko 向机器人发出指令 ,则机器人会将位置 的箱子移到位置 ,位置 的箱子移到位置 ,位置 的箱子移到位置 。操作后的箱子顺序将变为

请编写一个程序,设计必要的指令,使得机器人能够用最少的操作次数将给定的箱子序列排序。在此过程中,单次操作的长度(即需要循环移动的位置数量)并不重要。

输入格式

第一行输入一个整数 ,表示仓库中的箱子数量。

第二行包含 个不同的正整数,按顺序表示箱子的初始顺序标签。

输出格式

第一行输出一个整数 ,表示所需的最少操作次数。

接下来的 行每行描述一次操作:首先输出一个正整数表示该操作涉及的位置总数,接着是一个 : 字符、一个空格,然后按顺序列出需要循环移动的位置,各位置之间用一个空格分隔。

注意:解不一定唯一。如果存在多个可能的解,输出其中任意一个即可。

样例

样例输入 1

3 
3 2 1

样例输出 1

1
2: 3 1

样例输入 2

5 
2 3 1 5 4

样例输出 2

2 
3: 1 2 3 
2: 5 4 

样例输入 3

5 
1 2 3 4 5

样例输出 3

0

数据范围与提示

如果程序在某个测试用例中的操作次数不超过 但也并非最少的,只要能够正确排序就可以获得该测试点 的分数。