DMOPC '18 Contest 1 P3 - Sorting

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Bob has a permutation P of the integers 1, 2, 3,\ldots , N. Bob has recently learned how to sort but he only knows one operation. A shift operation is defined as a sequence of distinct indices, i_1, i_2, i_3,\ldots , i_k. After the indices are chosen, the element at i_1 moves to i_2, the element at i_2 moves to i_3, and so on. The element at i_k moves to i_1. Bob does not know how to sort efficiently yet, so please tell him how to sort the permutation in increasing order using the minimum number of shift operations. If there are multiple best solutions you may output any.

Constraints

In all subtasks:
1 \le N \le 100
1 \le P_i \le N
P_1, P_2, P_3, ... , P_N forms a permutation.

Subtask 1 [10%]

You will receive full points in this subtask as long as the shift operations correctly sort the permutation within 10\ 000 operations.
For this subtask, it does not need to be sorted in the minimal number of shift operations.

Subtask 2 [50%]

Suppose S is the maximum number of shift operations used in any test case of this subtask. Then:

  • If S> 100, your score for this subtask is 0.
  • If 50<S\le 100, your score for this subtask is \left \lfloor 40\cdot (\frac{100-S}{50}) + 10 \right \rfloor
  • If S\le 50, your score for this subtask is 50.

For this subtask, it does not need to be sorted in the minimal number of shift operations.

Subtask 3 [40%]

You will receive full points in this subtask only if you sort the permutation in the minimal number of shift operations possible.

Input Specification

The first line contains one integer, N.
The second line contains N space-separated integers, P_1, P_2, \ldots, P_N, the permutation.

Output Specification

On the first line output M, the number of shift operations needed to sort the permutation.
On the next M lines, output k followed by k space-separated distinct integers describing the indices of the shift operation.
Failure to follow output specifications will result in a Wrong Answer verdict.

Sample Input 1

6   
1 4 2 3 5 6

Sample Output 1

1   
3 2 4 3

Sample Input 2

4
2 1 4 3

Sample Output 2

2
2 1 2
2 3 4

Comments

There are no comments at the moment.