/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
非負整数のみからなる長さ N の数列 a,b が与えられます。a,b の i 番目の要素はそれぞれ a_i, b_i です。
非負整数 x が以下の条件を満たすとき、x を よい数 と呼びます。
- 条件：b を並べ替えて、1 \leq i \leq N を満たすどの整数 i についても a_i \text{ XOR } b_i = x が成立するようにすることができる。ここで、\text{XOR } はビットごとの排他的論理和である。
よい数を小さい方からすべて列挙してください。
\text{ XOR } とは
整数 x, y のビットごとの排他的論理和 x \text{ XOR } y は、以下のように定義されます。
- x \text{ XOR } y を二進表記した際の 2^k (k \geq 0) の位の数は、x, y を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 2000
- 0 \leq a_i, b_i < 2^{30}
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \cdots a_N b_1 \cdots b_N
出力
1 行目によい数の個数 K を出力せよ。 続けて K 行出力せよ。続く K 行の i 行目には小さい方から i 番目のよい数を出力せよ。
入力例 1
3 1 2 3 6 4 7
出力例 1
1 5
- b を (4, 7, 6) と並び替えたとき、a_1 \text{ XOR } b_1 = a_2 \text{ XOR } b_2 = a_3 \text{ XOR } b_3 = 5 となるため、5 はよい数です。他によい数はありません。
入力例 2
2 0 1 0 2
出力例 2
0
入力例 3
24 14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481 805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010
出力例 3
8 107543995 129376201 139205201 160626723 312334911 323172429 481902037 493346727
Score : 400 points
Problem Statement
Given are sequences a and b, each of length N, consisting of non-negative integers. The i-th elements of a and b are a_i and b_i, respectively.
A non-negative integer x is said to be good when the following condition is satisfied:
- Condition: It is possible to permute b so that a_i \text{ XOR } b_i = x holds for every integer i such that 1 \leq i \leq N, where \text{XOR } is the bitwise XOR.
List all good integers in ascending order.
What is \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers x and y, x\ \mathrm{XOR}\ y, is defined as follows:
- When x\ \mathrm{XOR}\ y is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of x and y is 1, and 0 otherwise.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 0 \leq a_i, b_i < 2^{30}
Input
Input is given from Standard Input in the following format:
N a_1 \cdots a_N b_1 \cdots b_N
Output
In the first line, print K, the number of good integers. Then, print K more lines. In the i-th of these K lines, print the i-th smallest good integer.
Sample Input 1
3 1 2 3 6 4 7
Sample Output 1
1 5
- If we permute b into (4, 7, 6), we have a_1 \text{ XOR } b_1 = a_2 \text{ XOR } b_2 = a_3 \text{ XOR } b_3 = 5, so 5 is a good integer. There are no other good integers.
Sample Input 2
2 0 1 0 2
Sample Output 2
0
Sample Input 3
24 14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481 805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010
Sample Output 3
8 107543995 129376201 139205201 160626723 312334911 323172429 481902037 493346727