分数: 900 点
问题陈述
我们有一个排列 P = P_0, P_1, \ldots, P_{N - 1} of 0, 1, \ldots, 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}
输出
如果无法排序 P 按升序排列,最多 2 \times 10^5 操作,打印 -1.
否则,打印 第一行中的 K + 1 行表示排序的操作序列 P 按升序排列,其中 K 是完成的操作数,如下:
- 第一行应包含整数 K;
- 这 (1 + i)-行 (1 \leq i \leq K) 应包含整数 j ~ (0 \leq j \leq N - 1) 中宣布 i第次操作。
您不必最小化已完成的操作数量。 如果最多有多个这样的序列 2 \times 10^5 操作,其中任何一个都将被接受。
示例输入 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.