No.1854 Limited Bubble Sort

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 21
作問者 :

蜜蜂 / テスター :

Mitarushi

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 を出力し、改行してください。

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

$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$ つめのテストケースについて、 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。