/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下の条件を満たす、長さ 2^{M + 1} の数列 a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} を、存在するならば 1 つ構築してください。
- a は 0 以上 2^M 未満の整数を、それぞれちょうど 2 つずつ含む。
- a_i = a_j を満たす任意の i,\ j \ (i < j) について、a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K である。
xor (排他的論理和) とは
整数 c_1, c_2, ..., c_n の xor は以下のように定義されます。
- c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n を二進表記した際の 2^k (k \geq 0) の位の数は、c_1, c_2, ..., c_n のうち二進表記した際の 2^k の位の数が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。
例えば、3 \ xor \ 5 = 6 です (二進表記すると: 011 xor 101 = 110 です)。
制約
- 入力は全て整数である。
- 0 \leq M \leq 17
- 0 \leq K \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
M K
出力
条件を満たす数列 a が存在しなければ -1 を出力せよ。
存在するならば、a の要素を空白区切りで出力せよ。
条件を満たす数列が複数存在する場合、どれを出力してもよい。
入力例 1
1 0
出力例 1
0 0 1 1
このケースでは、条件を満たす数列は複数存在します。
例えば a = {0, 0, 1, 1} の場合、a_i = a_j を満たす (i,\ j)\ (i < j) として (1, 2) と (3, 4) があります。a_1 \ xor \ a_2 = 0,\ a_3 \ xor \ a_4 = 0 であるため、この a は与えられた条件を満たしています。
入力例 2
1 1
出力例 2
-1
条件を満たす数列は存在しません。
入力例 3
5 58
出力例 3
-1
条件を満たす数列は存在しません。
Score : 600 points
Problem Statement
Construct a sequence a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} of length 2^{M + 1} that satisfies the following conditions, if such a sequence exists.
- Each integer between 0 and 2^M - 1 (inclusive) occurs twice in a.
- For any i and j (i < j) such that a_i = a_j, the formula a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K holds.
What is xor (bitwise exclusive or)?
The xor of integers c_1, c_2, ..., c_n is defined as follows:
- When c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.
For example, 3 \ xor \ 5 = 6. (If we write it in base two: 011 xor 101 = 110.)
Constraints
- All values in input are integers.
- 0 \leq M \leq 17
- 0 \leq K \leq 10^9
Input
Input is given from Standard Input in the following format:
M K
Output
If there is no sequence a that satisfies the condition, print -1.
If there exists such a sequence a, print the elements of one such sequence a with spaces in between.
If there are multiple sequences that satisfies the condition, any of them will be accepted.
Sample Input 1
1 0
Sample Output 1
0 0 1 1
For this case, there are multiple sequences that satisfy the condition.
For example, when a = {0, 0, 1, 1}, there are two pairs (i,\ j)\ (i < j) such that a_i = a_j: (1, 2) and (3, 4). Since a_1 \ xor \ a_2 = 0 and a_3 \ xor \ a_4 = 0, this sequence a satisfies the condition.
Sample Input 2
1 1
Sample Output 2
-1
No sequence satisfies the condition.
Sample Input 3
5 58
Sample Output 3
-1
No sequence satisfies the condition.