問題一覧 > 通常問題

No.1854 Limited Bubble Sort

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 21
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
0 ProblemId : 6727 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-26 00:09:30

問題文

$(1,2, \cdots , N)$ を並び替えた数列 $p$ が与えられます。はじめ、 $p$ の第 $i$ 項は $p_i$ です。

あなたの目的は $N^2$ 回以下操作を行い $p$ を昇順に並び替えることです。操作を行わなくても構いません。あなたは操作により以下のように $p$ を変更することができます。

  • $p$ の第 $i$ 項が $i$ でないかつ $p$ の第 $i+1$ 項が $i+1$ でないような整数 $i$ ( $1 \leq i \leq N-1$ ) を宣言し、 $p$ の第 $i$ 項と $p$ の第 $i+1$ 項を入れ替える。

あなたが目的を達成できるかを判別し、可能な場合は目的を達成する操作列を一つ示してください。
$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

入力

入力の $1$ 行目は以下の通りです。
$T$
そして、 $T$ 個のテストケースが続きます。これらはそれぞれ以下の形式で与えられます。
$N$
$p_1\ \ p_2\ \ \cdots \ \ p_N$

  • $1 \leq T \leq 250$
  • $2 \leq N \leq 500$
  • $1 \leq p_i \leq N$ ( $1 \leq i \leq N$ )
  • 入力は全て整数
  • $p$ は $(1,2, \cdots , N)$ を並び替えて得られる。
  • $1$ つの入力ファイルにおいて $N$ の総和は $500$ を超えない。

出力

目的を達成できない場合は -1 を出力し、改行してください。

目的を達成できる場合は以下のように出力し、改行してください。

$Q$
$a_1\ \ a_2\ \ \cdots \ \ a_Q$
ここで、 $Q$ は操作回数、 $a_x$ は $x$ 回目の操作で宣言した $i$ を表します。よって $0 \leq Q \leq N^2, 1 \leq a_i \leq N-1$ ( $1 \leq i \leq Q$ ) を満たす必要があります。

これを $T$ 個のテストケース全てに行ってください。

サンプル

サンプル1
入力
4
4
2 1 4 3
3
3 2 1
5
1 2 3 4 5
2
2 1
出力
2
3 1
-1
0

1
1

  • $1$ つめのテストケースについて、 $p$ は $(2,1,4,3) \rightarrow (2,1,3,4) \rightarrow (1,2,3,4)$ と変化します。
  • $2$ つめのテストケースについて、 $p$ に対して操作を行うことはできません。
  • $3$ つめのテストケースについて、 $p$ は最初から昇順に並び替えられています。
  • $4$ つめのテストケースについて、 $p$ は $(2,1) \rightarrow (1,2)$ と変化します。
  • 操作回数を最小化する必要はないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。