/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_{N}),B=(B_1,B_2,\ldots,B_{N}) が与えられます。
数列 A に対し以下の操作を 70000 回以下行うことで A を B に一致させられるか判定し、可能な場合は実際に操作手順を一つ示してください。
- 整数 K\ (1\le K \le N) を選ぶ。全ての i\ (2\leq i \leq K) について、 A_i の値を A_{i-1} \oplus A_i で置き換える。この置き換えは全ての i\ (2\leq i \leq K) に対して同時に行う。
ただしここで、\oplus はビット単位 \mathrm{XOR} 演算を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A,B のビット単位 \mathrm{XOR} 演算、A\oplus B は、以下のように定義されます。
- A\oplus B を二進表記した際の 2^k\ (k\geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3\oplus 5 = 6 となります（二進表記すると: 011\oplus 101 = 110)。
制約
- 2 \leq N \leq 1000
- 0 \leq A_i, B_i < 2^{60}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
70000 回以下の操作で A を B に一致させられない場合、No と出力せよ。一致させられる場合、操作回数を M 回とし、i 回目の操作で選んだ整数を K_i として以下の形式で出力せよ。
Yes M K_1 K_2 \ldots K_M
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 1 2 0 1 2 3
出力例 1
Yes 2 2 3
この出力例では、操作によって数列 A は以下のように変化します。
- 初期状態：A=(1, 2, 0)
- 1 回目の操作後：A=(1, 3, 0)
- 2 回目の操作後：A=(1, 2, 3)
2 回の操作後、A と B は一致しているのでこの出力は条件を満たします。
入力例 2
2 10 100 1 0
出力例 2
No
入力例 3
2 1152921504606846975 0 1152921504606846975 0
出力例 3
Yes 0
Score : 800 points
Problem Statement
You are given two sequences, each of length N, consisting of non-negative integers: A=(A_1,A_2,\ldots,A_{N}) and B=(B_1,B_2,\ldots,B_{N}).
Determine whether it is possible to make A equal to B by performing the operation below at most 70000 times. If it is possible, present a specific sequence of operations that achieves it.
- Choose an integer K\ (1\le K \le N). For every integer i\ (2\leq i \leq K), simultaneously replace the value of A_i with A_{i-1} \oplus A_i.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A\oplus B, is defined as follows:
- When A\oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B are 1, and 0 otherwise.
For example, 3\oplus 5 = 6 (in base two: 011\oplus 101 = 110).
Constraints
- 2 \leq N \leq 1000
- 0 \leq A_i, B_i < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
If it is impossible to make A equal to B in at most 70000 operations, print No. If it is possible, print a sequence of operations that achieves it in the following format, where M is the number of operations, and K_i is the integer chosen in the i-th operation:
Yes M K_1 K_2 \ldots K_M
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 1 2 0 1 2 3
Sample Output 1
Yes 2 2 3
In this output, the sequence A is changed as follows:
- Initially: A=(1, 2, 0).
- After the 1-st operation: A=(1, 3, 0).
- After the 2-nd operation: A=(1, 2, 3).
After the two operations, A and B are equal, achieving the objective.
Sample Input 2
2 10 100 1 0
Sample Output 2
No
Sample Input 3
2 1152921504606846975 0 1152921504606846975 0
Sample Output 3
Yes 0