No.1896 Arrays and XOR Procedure 2
タグ : / 解いたユーザー数 67
作問者 :
Shirotsume
/ テスター :
ygussany
とりゐ
問題文
長さが $N$ である $2$ つの数列 $A = (A_1, A_2, \dots, A_N)$ と $B = (B_1, B_2, \dots, B_N)$ が与えられます。
この $2$ つの数列に対して、以下に示す $2$ 種類の操作を行います。
操作1: $1 \leq P \leq N, 1 \leq Q \leq N$ を満たす $2$ つの整数 $(P, Q)$ を選ぶ。 $A_P$ を $A_P \oplus B_Q$ に置き替える。
操作2: $1 \leq P \leq N, 1 \leq Q \leq N$ を満たす $2$ つの整数 $(P, Q)$ を選ぶ。 $B_Q$ を $A_P \oplus B_Q$ に置き替える。
ただし、 $X \oplus Y$ は $X$ と $Y$ の Bitwise XOR を表します。
操作1および操作2を合わせて $0$ 回以上 $10000$ 回以下行うことで、以下の条件を満たしてください。
- $\max(A) < \min(B)$。すなわち、任意の $i, j$ $(1 \leq i \leq N, 1 \leq j \leq N)$ について $A_i < B_j$
この問題の制約下で、条件を満たす操作方法が必ず存在することが証明できます。また、操作回数を最小にする必要はありません。
Bitwise XOR とは（クリックで展開）
$2$ つの非負整数 $X, Y$ について、$X \oplus Y$ は以下のように定義されます。
- $X \oplus Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、$X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位のうちちょうど一方が $1$ である場合 $1$ 、そうでない場合 $0$
例えば、 $3 \oplus 5 = 6, 1 \oplus 1 = 0$ です。
制約
- 入力は全て整数
- $1 \leq N \leq 3000$
- $1 \leq A_i < 2^{30}$ ($1 \leq i \leq N$)
- $1 \leq B_i < 2^{30}$ ($1 \leq i \leq N$)
入力
入力は以下の形式で標準入力から与えられる。$N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$
出力
$1$ 行目には、操作を行う回数 $K$ $(0 \leq K \leq 10000)$ を出力せよ。その後、$2$ 行目から $K$ 行にわたって、行う操作を出力せよ。
各操作は $3$ つの整数 $T, P, Q$ で表すこと。$T$ は $1$ または $2$ で、$T = 1$ ならば $(P, Q)$ を選んで操作1を行うこと、$T = 2$ ならば $(P, Q)$ を選んで操作2を行うことを表す。
したがって、$i$ 回目の操作を $(T_i, P_i, Q_i)$ とすると出力は以下の形式となる。
$K$ $T_1$ $P_1$ $Q_1$ $T_2$ $P_2$ $Q_2$ $\vdots$ $T_K$ $P_K$ $Q_K$
条件を満たすことのできる操作列が複数存在する場合、どれを出力しても正解となる。
サンプル
サンプル1
入力
3 4 5 6 1 2 3
出力
4 2 3 1 2 2 2 1 3 2 2 1 3
初め、$A = (4, 5, 6), B = (1, 2, 3)$ です。まず、操作2を $(P, Q) = (3, 1)$ として行うと、$A = (4, 5, 6), B = (7, 2, 3)$ となります。
次に、操作2を $(P, Q) = (2, 2)$ として行うと、$A = (4, 5, 6), B = (7, 7, 3)$ となります。
次に、操作1を $(P, Q) = (3, 2)$ として行うと、$A = (4, 5, 1), B = (7, 7, 3)$ となります。
最後に、操作2を $(P, Q) = (1, 3)$ として行うと、 $A = (4, 5, 1), B = (7, 7, 7)$ となり、条件が満たせます。
以上より、 $4$ 回の操作で条件を満たすことができました。操作回数を最小にする必要はありません。
サンプル2
入力
4 1 2 3 4 5 6 7 8
出力
0
操作を行わなくても条件を満たしている場合があります。
サンプル3
入力
5 1 3 3 3 3 2 2 2 2 2
出力
4 1 2 2 1 3 3 1 4 4 1 5 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。