← 返回题目列表

AtCoder · asaporo2_b

B. 许多交换排序

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

分数: 900 点

问题陈述

Snuke 有一个序列 p,这是一个排列 (0,1,2, ...,N-1)。 的 i- 第一个元素 (0-索引)在 p is p_i.

他可以表演 N-1 标记的操作种类 1,2,...,N-1 以任意顺序任意次数。 当操作标记为 执行 k 时,将执行以下代码表示的过程:

for(int i=k;i<N;i++)
    swap(p[i],p[i-k]);

他想排序 p 按升序使用 0 和 10^{5} 操作(含)。 展示这样一个操作序列。 可以证明,在该问题的约束下,总是存在这样的操作序列。

约束

  • 2 \leq N \leq 200
  • 0 \leq p_i \leq N-1
  • p 是一个排列 (0,1,2,...,N-1).

部分分数 通过满足以下条件的测试集将获得

  • 在测试集中值得 300 点, N \leq 7.
  • 在测试集中值得另一个 400 点, N \leq 30.

输入

输入由标准输入按以下格式给出:

N
p_0 p_1 ... p_{N-1}

输出

让 m 是解决方案中的操作数。在第一行中,打印 m。 在 i- 以下各项 m 行,打印标签 i-第一个执行的操作。 解决方案将被接受,如果 m 最多是 10^5 和 p 执行后按升序排列 m 操作。


样本输入 1

5
4 2 0 1 3

示例输出 1

4
2
3
1
2
  • 每次操作都会改变 p 如下图:
9f3b51eb1fe742848f407bdeb7b772e1.png

示例输入 2

9
1 0 4 3 5 6 2 8 7

示例输出 2

11
3
6
1
3
5
2
4
7
8
6
3