問題一覧 > 通常問題

No.1896 Arrays and XOR Procedure 2

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 68
作問者 : Shirotsume / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 7406 / 自分の提出
問題文最終更新日: 2022-07-20 02:08:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 338 (順位表) の他の問題:

Problem Statement

You are given $2$ sequences of length $N$: $A = (A_1, A_2, \dots, A_N)$ and $B = (B_1, B_2, \dots, B_N)$.

On these $2$ sequences, you perform the $2$ types of operations described below.

    Operation 1: Choose $2$ integers $(P, Q)$ satisfying $1 \leq P \leq N, 1 \leq Q \leq N$. Replace $A_P$ with $A_P \oplus B_Q$.

    Operation 2: Choose $2$ integers $(P, Q)$ satisfying $1 \leq P \leq N, 1 \leq Q \leq N$. Replace $B_Q$ with $A_P \oplus B_Q$.

Here, $X \oplus Y$ denotes the Bitwise XOR of $X$ and $Y$.

By performing Operation 1 and Operation 2 at least $0$ and at most $10000$ times in total, satisfy the following condition.

  • $\max(A) < \min(B)$. That is, $A_i < B_j$ for all $i, j$ $(1 \leq i \leq N, 1 \leq j \leq N)$

It can be proved that under the constraints of this problem, a way of performing operations that satisfies the condition always exists. You do not need to minimize the number of operations.

What is Bitwise XOR? (click to expand)

For $2$ non-negative integers $X, Y$, $X \oplus Y$ is defined as follows.

  • The $2^k$ $(k \geq 0)$ place of $X \oplus Y$ in base $2$ is $1$ if exactly one of the $2^k$ place of $X$ in base $2$ and the $2^k$ place of $Y$ in base $2$ is $1$, and $0$ otherwise

For example, $3 \oplus 5 = 6, 1 \oplus 1 = 0$.

Constraints

  • All input values are integers
  • $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$)

Input

The input is given from Standard Input in the following format. 
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

Output

On the $1$ st line, print the number of operations $K$ $(0 \leq K \leq 10000)$ to perform. Then, on the $K$ lines starting from line $2$, print the operations to perform.

Each operation is represented by $3$ integers $T, P, Q$. $T$ is $1$ or $2$: $T = 1$ means performing Operation 1 with the chosen $(P, Q)$, and $T = 2$ means performing Operation 2 with the chosen $(P, Q)$.

Therefore, denoting the $i$-th operation by $(T_i, P_i, Q_i)$, the output has the following format.

$K$
$T_1$ $P_1$ $Q_1$
$T_2$ $P_2$ $Q_2$
$\vdots$
$T_K$ $P_K$ $Q_K$

If there are multiple sequences of operations that satisfy the condition, any of them will be accepted.

Sample

Sample 1
Input
3
4 5 6
1 2 3
Output
4
2 3 1
2 2 2
1 3 2
2 1 3

Initially, $A = (4, 5, 6), B = (1, 2, 3)$. First, performing Operation 2 with $(P, Q) = (3, 1)$ gives $A = (4, 5, 6), B = (7, 2, 3)$.

Next, performing Operation 2 with $(P, Q) = (2, 2)$ gives $A = (4, 5, 6), B = (7, 7, 3)$.

Next, performing Operation 1 with $(P, Q) = (3, 2)$ gives $A = (4, 5, 1), B = (7, 7, 3)$.

Finally, performing Operation 2 with $(P, Q) = (1, 3)$ gives $A = (4, 5, 1), B = (7, 7, 7)$, which satisfies the condition.

Thus, the condition was satisfied with $4$ operations. You do not need to minimize the number of operations.

Sample 2
Input
4
1 2 3 4
5 6 7 8
Output
0

The condition may already be satisfied without performing any operations.

Sample 3
Input
5
1 3 3 3 3
2 2 2 2 2
Output
4
1 2 2
1 3 3
1 4 4
1 5 5

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