/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
0, 1, \ldots, N - 1 を並び替えた数列 P = P_0, P_1, \ldots, P_{N - 1} があります。
あなたは P に対して、以下の操作を最大 2 \times 10^5 回まで行うことができます。
- 整数 i ~ (0 \leq i \leq N - 1) を宣言する。P_i と P_{(i + P_i) \textrm{ mod } N} を入れ替える
適切に操作を行うことで、P を昇順に並び替えてください。もしそれが不可能な場合、-1 を出力してください。
制約
- 入力は全て整数
- 2 \leq N \leq 100
- P は 0, 1, \ldots, N - 1 を並び替えた数列
入力
入力は以下の形式で標準入力から与えられる。
N
P_0 P_1 \ldots P_{N - 1}
出力
2 \times 10^5 回以下の操作で P を昇順に並び替えることが不可能な場合、-1 を出力せよ。
2 \times 10^5 回以下の操作で P を昇順に並び替えることが可能な場合、K 回操作を行うとして、以下の形式で K + 1 行出力せよ。
- 1 行目は整数 K
- 1 + i~(1 \leq i \leq K) 行目は、i 回目の操作で宣言する整数 j ~ (0 \leq j \leq N - 1)
操作回数を最小化する必要はない。 また、2 \times 10^5 回以下の操作で P を昇順に並び替える操作列が複数存在する場合、どれを出力しても構わない。
入力例 1
8 7 1 2 6 4 0 5 3
出力例 1
4 6 0 3 0
この操作列は、以下のように P を昇順に並び替えます。
-
まず i として 6 を宣言し、P_6 (= 5) と P_{(6 + 5) \textrm{ mod } 8} = P_3 (= 6) を入れ替える。P は 7, 1, 2, 5, 4, 0, 6, 3 になる
-
次に i として 0 を宣言し、P_0 (= 7) と P_{(0 + 7) \textrm{ mod } 8} = P_7 (= 3) を入れ替える。P は 3, 1, 2, 5, 4, 0, 6, 7 になる
-
次に i として 3 を宣言し、P_3 (= 5) と P_{(3 + 5) \textrm{ mod } 8} = P_0 (= 3) を入れ替える。P は 5, 1, 2, 3, 4, 0, 6, 7 になる
-
次に i として 0 を宣言し、P_0 (= 5) と P_{(0 + 5) \textrm{ mod } 8} = P_5 (= 0) を入れ替える。P は 0, 1, 2, 3, 4, 5, 6, 7 になる
Score : 900 points
Problem Statement
We have a permutation P = P_0, P_1, \ldots, P_{N - 1} of 0, 1, \ldots, N - 1.
You can do the following operation on P at most 2 \times 10^5 times:
- Announce an integer i ~ (0 \leq i \leq N - 1). Swap P_i and P_{(i + P_i) \textrm{ mod } N}.
Your task is to sort P in ascending order with this operation.
If it is impossible, print -1 instead.
Constraints
- All values in input are integers.
- 2 \leq N \leq 100
- P is a permutation of 0, 1, \ldots, N - 1.
Input
Input is given from Standard Input in the following format:
N
P_0 P_1 \ldots P_{N - 1}
Output
If it is impossible to sort P in ascending order with at most 2 \times 10^5 operations, print -1.
Otherwise, print K + 1 lines to represent a sequence of operations that sorts P in ascending order, where K is the number of operations done, as follows:
- The first line should contain the integer K;
- the (1 + i)-the line (1 \leq i \leq K) should contain the integer j ~ (0 \leq j \leq N - 1) announced in the i-th operation.
You do not have to minimize the number of operations done. If there are multiple such sequences of at most 2 \times 10^5 operations, any of them will be accepted.
Sample Input 1
8 7 1 2 6 4 0 5 3
Sample Output 1
4 6 0 3 0
This sequence of operations sorts P in ascending order, as follows:
-
First, announce i = 6. We swap P_6 (= 5) and P_{(6 + 5) \textrm{ mod } 8} = P_3 (= 6), turning P into 7, 1, 2, 5, 4, 0, 6, 3.
-
Then, announce i = 0. We swap P_0 (= 7) and P_{(0 + 7) \textrm{ mod } 8} = P_7 (= 3), turning P into 3, 1, 2, 5, 4, 0, 6, 7.
-
Then, announce i = 3. We swap P_3 (= 5) and P_{(3 + 5) \textrm{ mod } 8} = P_0 (= 3), turning P into 5, 1, 2, 3, 4, 0, 6, 7.
-
Finally, announce i = 0. We swap P_0 (= 5) and P_{(0 + 5) \textrm{ mod } 8} = P_5 (= 0), turning P into 0, 1, 2, 3, 4, 5, 6, 7.