← 返回题目列表

AtCoder · arc121_c

C. 奇偶排序

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

分数: 500 点

问题陈述

给定的是一个序列 p 这是一个排列 (1,2, \ldots, N)。 最初, n第 学期 p is p_{n}.

你的目标是排序 p 最多按升序排列 N^2 操作。 在一项操作中,您可以对 p:

  • 在 1-st, 3-rd 及后续 奇数 操作,您选择一个 奇数 n 之间 1 和 N-1 (含)进行交换 p_n 和 p_{n+1}.
  • 在 2-nd, 4-th 及后续 偶数 操作,您选择一个 偶数 n 之间 2 和 N-1 (含)进行交换 p_n 和 p_{n+1}.

我们可以证明,在这个问题的约束下,目标总是可以实现的。 找到实现目标的一系列操作。

你将得到 T 测试用例并要求解决每个用例。

约束

  • 输入中的所有值都是整数。
  • 1 \leq T \leq 250
  • 2 \leq N \leq 500
  • 1 \leq p_i \leq N
  • p 是一个排列 (1,2,\ldots,N).
  • 在一个输入文件中, N 不超过 500.

输入

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

T
\mathrm{case}_{1}
\vdots
\mathrm{case}_{T}

每个案例的格式如下:

N
p_1 \cdots p_N

输出

对于每个 T 测试用例,按照给出的顺序,按以下格式打印您的答案:

M
a_1 \cdots a_M

在这里, M 代表操作序列的长度,并且 a_i 代表您在中选择的整数 i-第次操作。

如果对于每个测试用例,您的操作序列都实现了目标,则您的输出将被视为正确。


示例输入 1

2
5
2 1 3 5 4
2
1 2

示例输出 1

2
1 4
0

  • 这是对 1-st 测试用例。
    • 选择 1 在 1-st 操作使得 p = (1,2,3,5,4).
    • 选择 4 在 2-nd 操作使得 p = (1,2,3,4,5).
    • 请注意,虽然 (1,4) 是有效的操作序列, (4, 1) 不是。
  • 还要注意的是,允许不执行任何操作,并且不要求最小化操作次数。