← 返回题目列表

AtCoder · arc110_f

F. Eso 交换

中文机器翻译题面 查看原题

分数: 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.