AtCoder Beginner Contest 126
F
XOR Matching
AtCoder
⌀ 1770
原题
← E→
翻译中…

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.

翻译中…

样例

Input #1
1 0
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.
Input #2
1 1
Output #2
-1
No sequence satisfies the condition.
Input #3
5 58
Output #3
-1
No sequence satisfies the condition.
题目信息
题号
abc126_f
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。