AT_arc121_c [ARC121C] Odd Even Sort

题目描述

给定一个由 $(1,2,\ldots,N)$ 组成的排列 $p$。初始时，$p$ 的第 $n$ 项为 $p_n$。

你的目标是在不超过 $N^2$ 次 操作 内将 $p$ 排成升序。你可以通过如下方式对 $p$ 进行操作：

• 在第奇数次操作时，你可以选择 $1$ 到 $N-1$ 之间的奇数 $n$，并交换 $p_n$ 和 $p_{n+1}$。
• 在第偶数次操作时，你可以选择 $2$ 到 $N-1$ 之间的偶数 $n$，并交换 $p_n$ 和 $p_{n+1}$。

在本题的限制下，总是可以实现目标。请给出一种满足条件的操作序列。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组测试数据格式如下：

$N$ $p_1$ $\cdots$ $p_N$

输出格式

对于每组测试数据，按输入顺序输出如下格式的答案：

$M$ $a_1$ $\cdots$ $a_M$

$M$ 表示操作序列的长度，$a_i$ 表示第 $i$ 次操作选择的整数。

只要输出的操作序列能使每组测试数据的 $p$ 排成升序，即为正确答案。

样例 1

输入

2
5
2 1 3 5 4
2
1 2

输出

2
1 4
0

说明/提示

限制

• 所有输入均为整数。
• $1 \leq T \leq 250$
• $2 \leq N \leq 500$
• $1 \leq p_i \leq N$
• $p$ 是 $(1,2,\ldots,N)$ 的一个排列。
• 单个输入文件中所有 $N$ 的总和不超过 $500$。

样例解释 1

• 对于第 1 组测试数据：
  • 第 1 次操作选择 $1$，此时 $p$ 变为 $(1,2,3,5,4)$。
  • 第 2 次操作选择 $4$，此时 $p$ 变为 $(1,2,3,4,5)$。
  • $(1,4)$ 是一个合法的操作序列，但 $(4,1)$ 不是。
  • 也可以不进行任何操作，并且不要求操作次数最少。

由 ChatGPT 4.1 翻译