C - Odd Even Sort 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

(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} を入れ替えます。

この問題の制約下で必ず目的を達成できることが証明できます。 そのような操作列を 1 つ求めてください。

T 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq T \leq 250
  • 2 \leq N \leq 500
  • 1 \leq p_i \leq N
  • p は (1,2,\ldots,N) を並び替えて得られる。
  • 1 つの入力ファイルにおいて 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 つ目のテストケースについて説明します。
    • 1 回目の操作で 1 を選ぶと p は (1,2,3,5,4) となります。
    • 2 回目の操作で 4 を選ぶと p は (1,2,3,4,5) となります。
    • (1,4) は操作列として正しいですが、(4,1) は操作列として正しくないことに注意してください。
  • 操作を 1 度も行わなくともよいこと、操作回数を最小にする必要はないことに注意してください。

Score : 500 points

Problem Statement

Given is a sequence p which is a permutation of (1,2, \ldots, N). Initially, the n-th term of p is p_{n}.

Your objective is to sort p in ascending order in at most N^2 operations. In one operation, you make the following change on p:

  • In the 1-st, 3-rd, and subsequent odd-numbered operations, you choose an odd number n between 1 and N-1 (inclusive) to swap p_n and p_{n+1}.
  • In the 2-nd, 4-th, and subsequent even-numbered operations, you choose an even number n between 2 and N-1 (inclusive) to swap p_n and p_{n+1}.

We can prove that the objective is always achievable under the Constraints of this problem. Find one sequence of operations that achieves the objective.

You will be given T test cases and asked to solve each of them.

Constraints

  • All values in input are integers.
  • 1 \leq T \leq 250
  • 2 \leq N \leq 500
  • 1 \leq p_i \leq N
  • p is a permutation of (1,2,\ldots,N).
  • In one input file, the sum of N does not exceed 500.

Input

Input is given from Standard Input in the following format:

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

Each case is in the following format:

N
p_1 \cdots p_N

Output

For each of the T test cases, in the order they are given, print your answer in the following format:

M
a_1 \cdots a_M

Here, M represents the length of your sequence of operations, and a_i represents the integer you choose in the i-th operation.

Your output will be considered correct if, for every test case, your sequence of operations achieves the objective.

Sample Input 1

2
5
2 1 3 5 4
2
1 2

Sample Output 1

2
1 4
0
  • Here is the description for the 1-st test case.
    • Choosing 1 in the 1-st operation makes p = (1,2,3,5,4).
    • Choosing 4 in the 2-nd operation makes p = (1,2,3,4,5).
    • Note that although (1,4) is a valid sequence of operations, (4, 1) is not.
  • Also note that it is allowed to perform no operation, and it is not required to minimize the number of operations.