問題一覧 > 通常問題

No.1896 Arrays and XOR Procedure 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 58
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ 👑 ygussanyygussany
1 ProblemId : 7406 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-08 11:29:15

問題文

長さが $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もしくは右上の雲マークをクリックしてアカウントを作成してください。