{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan class\u003d\"lang\"\u003e\n\u003cspan class\u003d\"lang-ja\"\u003e\n\u003ch1\u003eI: 偶奇ソート\u003c/h1\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e問題文\u003c/h3\u003e\u003cp\u003e$0$ から $N-1$ までの整数を並び替えた長さ $N$ の順列 $P$ が与えられます。\u003c/p\u003e\n\u003cp\u003e以下の操作を最大 $30$ 回まで行って、 $P$ を昇順に並べ替えてください。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e操作\u003c/h3\u003e\u003cp\u003e$1$ 回の操作では、次の 1 から 4 を順に行う。\u003c/p\u003e\n\u003col\u003e\n\u003cli\u003e\u003ccode\u003e0\u003c/code\u003e と \u003ccode\u003e1\u003c/code\u003e からなる長さ $N$ の文字列 $S$ と、整数 $t$ ( $t \u003d 0$ または $t \u003d 1$ ) を宣言する。\u003c/li\u003e\n\u003cli\u003e空の数列 $A, B$ を用意し、整数 $i$ を $1$ から $N$ まで動かしながら以下を行う。\u003cul\u003e\n\u003cli\u003e$S_i$ が \u003ccode\u003e0\u003c/code\u003e のとき、何もしない。\u003c/li\u003e\n\u003cli\u003e$S_i$ が \u003ccode\u003e1\u003c/code\u003e のとき、\u003cul\u003e\n\u003cli\u003e$P_i$ が偶数ならば $A$ の末尾に $P_i$ を追加する。\u003c/li\u003e\n\u003cli\u003e$P_i$ が奇数ならば $B$ の末尾に $P_i$ を追加する。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003cli\u003e数列 $C$ を以下のように定義する。\u003cul\u003e\n\u003cli\u003e$t \u003d 0$ のとき、 $C$ は $A$ と $B$ をこの順に連結したものとする。\u003c/li\u003e\n\u003cli\u003e$t \u003d 1$ のとき、 $C$ は $B$ と $A$ をこの順に連結したものとする。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003cli\u003e整数 $i$ を $1$ から $N$ まで動かしながら以下を行う。\u003cul\u003e\n\u003cli\u003e$S_i$ が \u003ccode\u003e0\u003c/code\u003e のとき、何もしない。\u003c/li\u003e\n\u003cli\u003e$S_i$ が \u003ccode\u003e1\u003c/code\u003e のとき、 $P_i$ を $C$ の先頭の要素に置き換え、 $C$ の先頭の要素を消す。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e例えば、$N \u003d 7, P \u003d {0, 4, 2, 3, 6, 5, 1}$ とします。\u003c/p\u003e\n\u003cp\u003e$S$ を \"1101101\" とし、$t \u003d 1$ とした操作を $1$ 回行うと、以下の図のように $P \u003d {3, 1, 2, 0, 4, 5, 6}$ となります。\u003c/p\u003e\n\u003cp\u003e\u003cimg alt\u003d\"parity-sort-example\" src\u003d\"CDN_BASE_URL/8d2e4c6fb30faacdf7e0c6cd44b8b8a7?v\u003d1714664588\"\u003e\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e制約\u003c/h3\u003e\u003cul\u003e\n\u003cli\u003e$1 \\leq N \\leq 15000$\u003c/li\u003e\n\u003cli\u003e$P$ は $0$ から $N-1$ までの整数を並び替えた順列\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"io-style\"\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力\u003c/h3\u003e\u003cp\u003e入力は以下の形式で標準入力から与えられる。\u003c/p\u003e\n\u003cpre\u003e$N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力\u003c/h3\u003e\u003cp\u003e$30$ 回以内の操作で $P$ を昇順に並べ替えるような操作列の $1$ つを以下の形式で出力せよ。このような操作列は複数存在するかもしれないが、どれを出力しても正答となる。\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e$1$ 行目には、操作を行う回数 $K$ を出力せよ。ただし、 $0 \\le K \\le 30$ でなければならない。\u003c/li\u003e\n\u003cli\u003e$i + 1$ 行目 $(1 \\le i \\le K)$ には、 $i$ 回目の操作で宣言する整数 $t_i (t_i \u003d 0,1)$ および長さ $N$ の文字列 $S_i$ をこの順に出力せよ。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cpre\u003e$K$\n$t_1$ $S_1$\n$t_2$ $S_2$\n$\\vdots$\n$t_K$ $S_K$\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例1\u003c/h3\u003e\u003cpre\u003e7\n0 4 2 3 6 5 1\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例1\u003c/h3\u003e\u003cpre\u003e1\n1 0100101\n\u003c/pre\u003e\n\n\u003cp\u003e操作を行うと、$A \u003d { 4, 6 }, B \u003d { 1 }$ となり、 $t \u003d 1$ より $C \u003d { 1, 4, 6 }$ となります。\u003c/p\u003e\n\u003cp\u003e$P$ の要素を $C$ によって置き換えると、 $P \u003d { 0, 1, 2, 3, 4, 5, 6 }$ となるので、この操作で $P$ を昇順に並べ替えることができます。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例2\u003c/h3\u003e\u003cpre\u003e4\n1 0 3 2\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例2\u003c/h3\u003e\u003cpre\u003e2\n0 1100\n0 0011\n\u003c/pre\u003e\n\n\u003cp\u003e例えば以下のような出力も正答となります。\u003c/p\u003e\n\u003cpre\u003e2\n0 1111\n1 0110\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例3\u003c/h3\u003e\u003cpre\u003e1\n0\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例3\u003c/h3\u003e\u003cpre\u003e0\n\u003c/pre\u003e\n\n\u003cp\u003e操作を行わなくても構いません。\u003c/p\u003e\u003c/section\u003e\n\u003c/div\u003e\n\u003c/span\u003e\n\u003c/span\u003e\n"}}]}