Problem:
 Score : 800 points    Problem Statement You are given integers N,\ A and B .
Determine if there exists a permutation (P_0,\ P_1,\ ...\ P_{2^N-1}) of (0,\ 1,\ ...\ 2^N-1) that satisfies all of the following conditions, and create one such permutation if it exists.   P_0=A  P_{2^N-1}=B  For all 0 \leq i < 2^N-1 , the binary representations of P_i and P_{i+1} differ by exactly one bit.       Constraints  1 \leq N \leq 17  0 \leq A \leq 2^N-1  0 \leq B \leq 2^N-1  A \neq B  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A  B       Output If there is no permutation that satisfies the conditions, print NO .  If there is such a permutation, print YES in the first line.
Then, print (P_0,\ P_1,\ ...\ P_{2^N-1}) in the second line, with spaces in between.
If there are multiple solutions, any of them is accepted.        Sample Input 1 2 1 3      Sample Output 1 YES
1 0 2 3  The binary representation of P=(1,0,2,3) is (01,00,10,11) , where any two adjacent elements differ by exactly one bit.       Sample Input 2 3 2 1      Sample Output 2 NO

Solution (Python):
def differ_by_1bit(n,end):
    if n==1:
        return [0,1]
    list=differ_by_1bit(n-1,0)
    for i in range(len(list)):
        q=list[i]//2**end
        r=list[i]%2**end
        list[i]=q*2**(end+1)+r
    list2=[2**end+list[-i-1] for i in range(len(list))]
    return list+list2

def differ_by_1bit_all(n):
    if n==1:
        return [0,1]
    if n%2==1:
        list1=differ_by_1bit_all(n-1)
        list2=differ_by_1bit(n-1,n-2)
        list2=[list2[i]^(2**(n-1)+2**(n-2)-1) for i in range(len(list2))]
        return list1+list2
    else:
        list1=differ_by_1bit(n-1,n-2)
        list1=[list1[i]<<1 for i in range(len(list1))]
        list2=differ_by_1bit_all(n-1)
        list2=[(list2[i]<<1)^(2**(n-1)+1) for i in range(len(list2))]
        return list1+list2

def convert(n,table):
    res=0
    for i in range(len(table)):
        if n>>i &1==1:
            res+=2**table[i]
    return res

def differ_by_1bit_free(n,end):
    T=[]
    F=[]
    for i in range(n):
        if end>>i &1==1:
            T.append(i)
        else:
            F.append(i)
    t=len(T)
    f=len(F)
    if t==n:
        return differ_by_1bit_all(n)
    list1=differ_by_1bit(f,0)
    list2=differ_by_1bit_all(t)
    res=[]
    for i in range(2**t):
        if i%2==0:
            res+=list1
        else:
            res+=list1[::-1]
    for i in range(2**n):
        res[i]=convert(res[i],F)
    for i in range(2**t):
        c=convert(list2[i],T)
        for j in range((2**f)*i,(2**f)*(i+1)):
            res[j]=res[j]^c
    return res

N,A,B=map(int,input().split())
test=B^A
check=0
for i in range(N):
    if test>>i &1==1:
        check+=1
if check%2==0:
    print("NO")
else:
    ans=differ_by_1bit_free(N,test)
    for i in range(len(ans)):
        ans[i]=ans[i]^A
    print("YES")
    print(*ans)

Solution (Python):
def main():
    n, a, b = map(int, input().split())
    if (bin(a).count("1")+bin(b).count("1")) % 2 == 0:
        print("NO")
        return
    print("YES")

    def calc(a, b, k):
        if k == 1:
            return [a, b]
        for i in range(k):
            if ((a >> i) & 1) ^ ((b >> i) & 1):
                break
        a2 = (a & (2**i-1))+((a >> (i+1)) << i)
        b2 = (b & (2**i-1))+((b >> (i+1)) << i)
        a3 = ((a >> i) & 1)
        b3 = ((b >> i) & 1)
        c = a2 ^ 1
        q = calc(a2, c, k-1)
        r = calc(c, b2, k-1)
        q = [((t >> i) << i+1)+(a3 << i)+(t & (2**i-1)) for t in q]
        r = [((t >> i) << i+1)+(b3 << i)+(t & (2**i-1)) for t in r]
        return q+r
    print(*calc(a, b, n))


main()

Solution (Python):
def main():
    n, a, b = map(int, input().split())
    if (bin(a).count("1")+bin(b).count("1")) % 2 == 0:
        print("NO")
        return
    print("YES")

    def calc(a, b, k):
        if k == 1:
            return [a, b]
        for i in range(k):
            if ((a >> i) & 1) ^ ((b >> i) & 1):
                break
        a2 = (a & (2**i-1))+((a >> (i+1)) << i)
        b2 = (b & (2**i-1))+((b >> (i+1)) << i)
        a3 = ((a >> i) & 1)
        b3 = ((b >> i) & 1)
        c = a2 ^ 1
        q = calc(a2, c, k-1)
        r = calc(c, b2, k-1)
        q = [((t >> i) << i+1)+(a3 << i)+(t & (2**i-1)) for t in q]
        r = [((t >> i) << i+1)+(b3 << i)+(t & (2**i-1)) for t in r]
        return q+r
    print(*calc(a, b, n))


main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
def bit(xx):return [format(x,"b") for x in xx]
popcnt=lambda x:bin(x).count("1")

def solve(xx,a,b):
    if len(xx)==2:return [a,b]
    k=(a^b).bit_length()-1
    aa=[]
    bb=[]
    for x in xx:
        if (x>>k&1)==(a>>k&1):aa.append(x)
        else:bb.append(x)
    i=0
    mid=aa[i]
    while mid==a or (mid^1<<k)==b or popcnt(a)&1==popcnt(mid)&1:
        i+=1
        mid=aa[i]
    
    return solve(aa,a,mid)+solve(bb,mid^1<<k,b)

def main():
    n,a,b=MI()
    if (popcnt(a)&1)^(popcnt(b)&1)==0:
        print("NO")
        exit()

    print("YES")
    print(*solve(list(range(1<<n)),a,b))

main()

Solution (Python):
n,a,b = map(int,input().split())
if bin(a^b).count("1")%2 == 0:
  print("NO")
  exit()
st = min(a,b)
dif = a^b
t = 1<<(n-1)
chls = []
chcnt = n-1
for i in range(n)[::-1]:
  if dif&1<<i:
    chls.append((chcnt,i))
    chcnt -= 1
def change(x,p,q):
  if (x>>p)&1 ^ (x>>q)&1:
    x ^= (1<<p)+(1<<q)
  return x
def changeall(x):
  for l,r in chls[::-1]:
    x = change(x,l,r)
  x ^= st
  return x
if n == 1:
  print("YES")
  print(a,b)
  exit()
ls = []
x = 0
for i in range(1,2**n):
  cnt = 0
  while i%2 == 0:
    i //= 2
    cnt += 1
  ls.append(1<<cnt)
chcnt += 1
while chcnt < n-1:
  i = chcnt+1
  ls[-2**i] //= 2
  ls[-2**(i-1)] *= 2
  ls[-2**(i-1)-2**i] *= 2
  chcnt += 2
nls = [0]
for i in ls:
  nls.append(nls[-1]^i)
print("YES")
ansls = [changeall(nls[i]) for i in range(2**n)]
if a < b:
  print(*ansls)
else:
  print(*ansls[::-1])

Solution (Python):
def popcnt(num):
    return bin(num).count('1')


def solve(n, a, b):
    c = a ^ b
    
    if popcnt(c) % 2 == 0:
        print('NO')
        exit(0)
    return [i ^ a for i in solve2(n, c)]


def solve2(n, c):
    c_1 = popcnt(c)
    d = (1 << c_1) - 1  
    ret_d = solve3(n, d, c_1)
    ret_c = move(ret_d, n, d, c)
    return ret_c


def solve3(n, d, cnt):
    if n == cnt:
        return solve4(n)
    ret = []
    a = graycode(n - cnt)
    a_rev = a[::-1]
    b = solve4(cnt)
    flg = True
    for i in b:
        if flg:
            for j in a:
                ret.append(merge(j, i, cnt))
        else:
            for j in a_rev:
                ret.append(merge(j, i, cnt))
        flg = not flg
    return ret


def solve4(n):
    if n == 1:
        return [0, 1]
    
    
    ret = graycode(n - 1) + [(1 << (n - 1)) | i for i in solve(n - 1, 1 << n - 2, mask(n - 1))]
    return ret


def graycode(n):
    ret = []
    for i in range(1 << n):
        ret.append(i ^ (i >> 1))
    return ret


def move(lst, n, d, c):
    l = [-1] * n
    c_0, c_1 = popcnt(c), 0
    for i in range(n):
        if c & (1 << i):
            l[c_1] = i
            c_1 += 1
        else:
            l[c_0] = i
            c_0 += 1
    ret = []
    for i in lst:
        k = 0
        for j in range(n):
            if i & (1 << j):
                k |= 1 << l[j]
        ret.append(k)
    return ret


def merge(a, b, margin):
    return (a << margin) + b


def mask(n):
    return (1 << n) - 1

n,a,b = map(int,input().split())
res = solve(n, a, b)
print('YES')
print(*res)

Solution (Python):
def extract(a, i):
  return (a>>(i+1) << i) | (a&((1<<i)-1))

def space(a, i):
  return ((a>>i) << (i+1)) | (a&((1<<i)-1))

def compose(n, a, b):
  if n==1:
    return [a, b]
  for i in range(n):
    if (a>>i&1) ^ (b>>i&1):
      x = i
      a_bool = (a>>i & 1) << i
      b_bool = a_bool ^ (1 << i)
      a_dash = extract(a, i)
      b_dash = extract(b, i)
      c = a_dash ^ 1
      break
  Q = compose(n-1, a_dash, c)
  R = compose(n-1, c, b_dash)
  n_Q = [space(i, x)|a_bool for i in Q]
  n_R = [space(i, x)|b_bool for i in R]
  return n_Q + n_R
  
n, a, b = map(int, input().split())
cnt = 0
c = a^b
for i in range(n):
  cnt += c>>i & 1
if cnt&1:
  print("YES")
  print(*compose(n, a, b))
else:
  print("NO")

Solution (Python):
def extract(a, i):
  return (a>>(i+1) << i) | (a&((1<<i)-1))

def space(a, i):
  return ((a>>i) << (i+1)) | (a&((1<<i)-1))

def compose(n, a, b):
  if n==1:
    return [a, b]
  for i in range(n):
    if (a>>i&1) ^ (b>>i&1):
      x = i
      a_bool = (a>>i & 1) << i
      b_bool = a_bool ^ (1 << i)
      a_dash = extract(a, i)
      b_dash = extract(b, i)
      c = a_dash ^ 1
      break
  Q = compose(n-1, a_dash, c)
  R = compose(n-1, c, b_dash)
  n_Q = [space(i, x)|a_bool for i in Q]
  n_R = [space(i, x)|b_bool for i in R]
  return n_Q + n_R
  
n, a, b = map(int, input().split())
cnt = 0
c = a^b
for i in range(n):
  cnt += c>>i & 1
if cnt&1:
  print("YES")
  print(*compose(n, a, b))
else:
  print("NO")

Solution (Python):

"""
ハミング距離がちょうど1
絶対不可能なのは、AとBの1の数の偶奇が違うとき
それ以外は可能か？

可能と仮定して構成法を考えてみる
ハミング距離を1だけ変化させる方法
→2**xを xorする

AとBが1桁だけ違う場合は可能、それ以外は不可能？
→1回だけ選ぶ桁は1つしかないのでおｋそう

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ

N=1 → 必ずハミング1になる
N=2 → 必ずハミング1になる
N=3 →

ある桁にxorするのを考える
1,0良い感じに分配→2個セットで分配してく
1個小さいの奴より2倍以上になってはダメ

差が2以下になるように分配可能
→分配したらどう取るか分かれば解ける

残り数が最大に奴から見ていく→未出ならやっちゃえばいい
たぶん行ける…たぶん…

→むりだった()

========ちょっとだけ解説を見た==========
ハミング距離が偶数なら無理、奇数なら可能

証明しよう
N = 1,2 の時　全列挙で自明
N >= 3のとき、そのN-1以下で全て成立すると仮定すると

0(0*(N-1))→0(ハミング奇数ALL)→1(ハミング奇数ALL)→1(ハミング偶数ALL)
となるので、ハミング奇数の奴をすべて構成できる(1の位置を途中に入れればすべて可能)

この考え方をどうやって構成に応用する？
→再帰っぽい
→またはdp?

小さい桁から合わせていく？

=========解説を見ました=============

再帰かぁ
やることは→始点と終点で違うbitを見つける
→そこで分割→始点未確定から1bitずらしたやつを前半終点・後半始点に据えて問題を2分割
必要なのは？→確定したbitを保持する変数
"""
import sys
d2lis = {}
for i in range(20):
    d2lis[2**i] = i

def f(start,goal,usedbit):

    
    nuse = 0
    for i in range(N):
        if ( ( (2**i) & usedbit == 0) and (start&(2**i) != goal&(2**i)) ):
            usedbit |= 2**i
            nuse = 2**i
            break

    

    flag = False
    for i in range(N):
        if ((2**i) & usedbit == 0):
            flag = True
            mids = start ^ (2**i)
            midg = mids  ^ nuse
            break

    if not flag:
        return [start,goal]
    else:
        ret = f(start,mids,usedbit) + f(midg,goal,usedbit)
        return ret 

N,A,B = map(int,input().split())




numbit = 0
for i in range(N):
    if ((A^B) & (2**i)) > 0:
        numbit += 1
if numbit % 2 == 0:
    print ("NO")
    sys.exit()

ans = f(A,B,0)

if len(ans) != 2**N:
    print ("NO")
    sys.exit()
for i in range(2**N-1):
    if abs(ans[i+1]-ans[i]) not in d2lis:
        print ("NO")
        sys.exit()

print ("YES")
print (" ".join(map(str,ans)))





"""
import sys

N,A,B = map(int,input().split())

lis = [[0,i] for i in range(N)]
able = [True] * (2**N)
rem = 2**N-1

for i in range(N):
    if (A^B) & (2**i) > 0:
        lis[i][0] += 1
        rem -= 1

if rem % 2 == 1:
    print ("NO")
    sys.exit()

lis.sort()

for i in range(rem//2):
    lis[i % N][0] += 2

ans = []

able[B] = False

for loop in range(2**N-1):

    if loop == 0:
        pass
    else:
        lis.sort()
        for i in range(N-1,-1,-1):
            if able[A ^ (2 ** lis[i][1])]:
                lis[i][0] -= 1
                if lis[i][0] < 0:
                    print ("NO")
                    sys.exit()
                A ^= 2 ** lis[i][1]
                break
        
    ans.append(A)
    able[A] = False

ans.append(B)
print ("YES")
print (" ".join(map(str,ans)))
"""


"""
import sys

def want_min(x):

    for i in range(20):
        if (2**i)&x > 0:
            return i

d2lis = {}

for i in range(20):
    d2lis[2**i] = i

N,A,B = map(int,input().split())


if A^B not in d2lis:
    print ("NO")
    sys.exit()

print ("YES")

upk = d2lis[A^B]
ans = []

for i in range(2**N):

    if i == 0:
        ans.append(A)
    elif i == 2 ** (N-1):
        A ^= 2 ** upk
        ans.append(A)
    else:
        keta = want_min(i)
        if keta >= upk:
            keta += 1
        A ^= 2**keta
        ans.append(A)

    


print (" ".join(map(str,ans)))

"""

Solution (Python):
import sys
input = sys.stdin.readline

N, A, B = map(int, input().split())

remain = []
must_change = []
for n in range(N):
    if (A^B)&(1<<n):
        must_change.append(n)
    else:
        remain.append(n)

ans = []
def dfs(ind, bit, end):
    if ind == 0:
        n = must_change[0]
        bit = dfs(ind+1, bit, False)
        bit = dfs(ind+1, bit^(1<<n), True)
    elif ind < len(must_change):
        n1, n2 = must_change[ind], must_change[ind+1]
        if end:
            bit = dfs(ind+2, bit, False)
            bit = dfs(ind+2, bit^(1<<n2), False)
            bit = dfs(ind+2, bit^(1<<n1), False)
            bit = dfs(ind+2, bit^(1<<n2), True)
        else:
            bit = dfs(ind+2, bit, False)
            bit = dfs(ind+2, bit^(1<<n1), False)
            bit = dfs(ind+2, bit^(1<<n2), False)
            bit = dfs(ind+2, bit^(1<<n1), False)
    elif ind < N:
        n = remain[ind-len(must_change)]
        bit = dfs(ind+1, bit, end)
        bit = dfs(ind+1, bit^(1<<n), end)
    else:
        ans.append(bit)
    
    return bit


if len(must_change)%2 == 0:
    print("NO")
else:
    dfs(0, A, False)
    print("YES")
    print(*ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, A, B = list(map(int, sys.stdin.buffer.readline().split()))






def bitcount(n):
    ret = 0
    while n > 0:
        ret += n & 1
        n >>= 1
    return ret












def solve(n, a, b):
    if n <= 0:
        return []
    if bitcount(a ^ b) % 2 == 0:
        return []
    if n == 1:
        return [a, b]
    
    
    mask = 1
    while (a ^ b) & mask == 0:
        mask <<= 1
    r_mask = mask - 1
    l_mask = ~mask - r_mask
    na = ((a & l_mask) >> 1) + (a & r_mask)
    nb = ((b & l_mask) >> 1) + (b & r_mask)
    mid = na ^ 1
    ret = []
    for r in solve(n - 1, na, mid):
        ret.append(((r << 1) & l_mask) + (a & mask) + (r & r_mask))
    for r in solve(n - 1, mid, nb):
        ret.append(((r << 1) & l_mask) + (b & mask) + (r & r_mask))
    return ret


ans = solve(N, A, B)
if ans:
    print('YES')
    print(*ans)
else:
    print('NO')

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, A, B = list(map(int, sys.stdin.buffer.readline().split()))






def bitcount(n):
    ret = 0
    while n > 0:
        ret += n & 1
        n >>= 1
    return ret












def solve(n, a, b):
    if n <= 0:
        return []
    if bitcount(a ^ b) % 2 == 0:
        return []
    if n == 1:
        return [a, b]
    
    
    mask = 1
    while (a ^ b) & mask == 0:
        mask <<= 1
    na = a // (mask << 1) * mask + a % mask
    nb = b // (mask << 1) * mask + b % mask
    mid = na ^ 1
    ret = []
    for r in solve(n - 1, na, mid):
        ret.append((r // mask * mask << 1) + (a & mask) + r % mask)
    for r in solve(n - 1, mid, nb):
        ret.append((r // mask * mask << 1) + (b & mask) + r % mask)
    return ret


ans = solve(N, A, B)
if ans:
    print('YES')
    print(*ans)
else:
    print('NO')

Solution (Python):
d = ((0, 0), (0, 1), (1, 1), (1, 0))
n, a, b = map(int, input().split())
c = 0
p = a ^ b
z, o = [], []
for i in range(n):
    if (p >> i) & 1:
        o.append(i)
    else:
        z.append(i)
if len(o) % 2 == 0:
    print('NO')
    exit(0)
print('YES')
ans = [0] * pow(2, n)
if n % 2:
    i = o.pop()
    for j in range(pow(2, n - 1), pow(2, n)):
        ans[j] += pow(2, i)
else:
    i = o.pop()
    j = z.pop()
    for k in range(4):
        tmp = pow(2, n) // 4
        for l in range(tmp):
            ans[k * tmp + l] += pow(2, i) * d[k][0] + pow(2, j) * d[k][1]
t = 1
while o:
    tmp = pow(2, n) // t // 8
    i = o.pop()
    j = o.pop()
    idx = 0
    for l in range(tmp):
        if l == 0:
            for p in range(4):
                for q in range(t):
                    ans[idx] += d[p][0] * \
                        pow(2, i) + d[p][1] * pow(2, j)
                    idx += 1
            for p in range(4):
                for q in range(t):
                    ans[idx] += d[p - 1][0] * \
                        pow(2, i) + d[p - 1][1] * pow(2, j)
                    idx += 1
        else:
            for p in range(4):
                for q in range(t):
                    ans[idx] += d[p - 2][0] * \
                        pow(2, i) + d[p - 2][1] * pow(2, j)
                    idx += 1
            for p in range(4):
                for q in range(t):
                    ans[idx] += d[1 - p][0] * \
                        pow(2, i) + d[1 - p][1] * pow(2, j)
                    idx += 1
    t *= 4
while z:
    tmp = pow(2, n) // t // 8
    i = z.pop()
    j = z.pop()
    idx = 0
    for l in range(tmp):
        for p in range(4):
            for q in range(t):
                ans[idx] += d[p][0] * \
                    pow(2, i) + d[p][1] * pow(2, j)
                idx += 1
        for p in range(4):
            for q in range(t):
                ans[idx] += d[3 - p][0] * \
                    pow(2, i) + d[3 - p][1] * pow(2, j)
                idx += 1
    t *= 4
print(' '.join(map(lambda x: str(x ^ a), ans)))

Solution (Python):
import sys
readline = sys.stdin.readline

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

P1 = [0, 2, 3, 1, 1, 3, 2, 0]
P2 = [0, 2, 3, 1, 1, 0, 2, 3]
Q = [0, 1, 1, 0]
def grey(N, K):
    if K%2 == 0:
        return False
    if N == 1:
        return [0, 1]
    if N == 2:
        return [0, 2, 3, 1]
    
    if N == K:
        L = grey(N-2, K-2)
        P = P1*((1<<(N-3))-1) + P2
        return [(1<<(N-2))*P[i]|L[i//4] for i in range(1<<N)]
    
    L = grey(N-1, K)
    return [(1<<(N-1))*Q[i%4]|L[i//2] for i in range(1<<N)]

def calc(N, y):
    k = popcount(y)
    pu = [0]*N
    cnt0 = k
    cnt1 = 0
    for i in range(N):
        if (1<<i)&y:
            pu[cnt1] = i
            cnt1 += 1
        else:
            pu[cnt0] = i
            cnt0 += 1
    return pu

def restore(N, x, pu):
    res = 0
    for i in range(N):
        if (1<<i)&x:
            res |= 1<<pu[i]
    return res
    
    
N, A, B = map(int, readline().split())

K = popcount(A^B)
Ans = grey(N, K)

if Ans:
    pu = calc(N, A^B)
    Ans = [A^(restore(N, a, pu)) for a in Ans]
    print('YES')
    print(*Ans)
else:
    print('NO')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def parity_onebit(x):
        return bin(x).count("1") & 1

    def make_route(s, g, state):
        if state.count(-1) == 1:
            return [s, g]
        sep_dig = bin(s ^ g)[::-1].find("1")
        s_bit = (s >> sep_dig) & 1
        Lstate = state[:]
        Rstate = state[:]
        Lstate[sep_dig] = s_bit
        Rstate[sep_dig] = 1 - s_bit
        for i in range(16):
            ng = 0
            i_copy = i
            for sk in Lstate[::-1]:
                ng <<= 1
                if sk == -1:
                    ng += i_copy & 1
                    i_copy >>= 1
                else:
                    ng += sk
            ns = ng ^ (1 << sep_dig)
            if ng != s and parity_onebit(ng) != parity_onebit(s) and ns != g:
                break
        res = make_route(s, ng, Lstate)
        state[sep_dig] = 1 - s_bit
        res += make_route(ns, g, Rstate)
        return res

    n, s, g = map(int, input().split())
    if parity_onebit(s) == parity_onebit(g):
        print("NO")
        exit()
    ans=make_route(s, g, [-1] * n)
    print("YES")
    print(*ans)
    

main()

Solution (Python):
N, A, B = map(int, input().split())

if N == 1:
    print('YES')
    print(A, B)
    exit()

A_bin = bin(A)
B_bin = bin(B)
one_A = 0
one_B = 0
for a in A_bin:
    if a == '1':
        one_A += 1
for b in B_bin:
    if b == '1':
        one_B += 1
if (one_A + one_B) % 2 == 0:
    print('NO')
    exit()
else:
    print('YES')

A_ori = A
A = A_ori ^ A
B = A_ori ^ B

nxt = {0: 1}
last = 1
for n in range(1, N):
    i = 0
    p = 2**n
    while True:
        if i == B-p:
            tmp = []
            while True:
                tmp.append(i+p)
                if i == last:
                    break
                else:
                    i = nxt[i]
            j = last
            for k in range(len(tmp)-1, -1, -1):
                nxt[j] = tmp[k]
                j = tmp[k]
            last = B
            break

        j = nxt[i]
        nxt[i] = i + p
        nxt[i+p] = j+p
        nxt[j+p] = j
        if j == last:
            break
        else:
            i = nxt[j]

i = 0
while True:
    print(i ^ A_ori)
    if i == last:
        break
    i = nxt[i]

Solution (Python):
import sys
input = sys.stdin.readline

N,A,B = map(int,input().split())

def seq(start,bits):
    arr = [0]
    for i in bits:
        arr += [x^(1<<i) for x in arr[::-1]]
    return [x^start for x in arr]

def solve(A,B,rest):
    if len(rest) == 1:
        return [A,B]
    if len(rest) == 2:
        i,j = rest
        x,y = 1<<i,1<<j
        if A^x == B:
            return [A,A^y,A^x^y,B]
        elif A^y == B:
            return [A,A^x,A^x^y,B]
        else:
            return None
    diff_bit = [i for i in rest if (A&(1<<i)) != (B&(1<<i))]
    if len(diff_bit) % 2 == 0:
        return None
    i = diff_bit[0]
    rest = [j for j in rest if j != i]
    if A^(1<<rest[0])^(1<<i) == B:
        rest[0],rest[1] = rest[1],rest[0]
    arr = seq(A,rest)
    return arr + solve(arr[-1]^(1<<i),B,rest)

rest = list(range(N))
answer = solve(A,B,rest)

if answer is None:
    print('NO')
else:
    print('YES')
    print(' '.join(map(str,answer)))

Solution (Python):
def num_of_1bit(n: int)->int:
    '''n の立っているビットを数えます。
    :param n: number
    :return: number of 1 bit
    '''
    s = 0
    while n > 0:
        s += n & 1
        n >>= 1
    return s


def diff_idx(a: int, b: int)->int:
    '''a と b のビット列を比較してビットの状態が異なる最小の
    インデックスを返します。ここで、インデックスは 2^i の i 
    に対応する。
    :param a: number 1
    :param b: number 2
    :return: index
    '''
    if a == b:
        return -1
    idx = 0
    while a > 0 or b > 0:
        if a & 1 != b & 1:
            break
        idx += 1
        a, b = a >> 1, b >> 1
    return idx


def remove_bit(n: int, idx: int)->int:
    '''n の idx 番目のビットを消去します。idx は 2^idx に対
    応します。
    ex) n = 1011011, idx = 2
    -> 101111

    :param n: number
    :param idx: index
    :return: number removed `idx`th bit
    '''
    upper = (n >> (idx+1)) << idx
    lower = n & ((1 << idx) - 1)
    return upper | lower


def insert_bit(n: int, idx: int, bit: bool)->int:
    '''n の idx 番目にビットを挿入します。
    ex) n = 101111, idx = 2, bit = True
    -> 1011111
    '''
    upper = (n >> idx) << (idx + 1)
    lower = n & ((1 << idx) - 1)
    insert = bit << idx
    return upper | insert | lower


def route(_from: int, to: int, N: int)->list:
    '''_from から to に至る N ビットの数を全て使ったルートを
    計算します。
    :param _from: start
    :param to: end
    :param N: number of bit
    :return: routes
    '''
    if N == 1:
        return [_from, to]

    di = diff_idx(_from, to)

    a = remove_bit(_from, di)
    b = remove_bit(to, di)
    c = a ^ 1

    from_bit = (_from & (1 << di)) != 0
    to_bit = (to & (1 << di)) != 0

    first_half = map(lambda x: insert_bit(x, di, from_bit), route(a, c, N-1))
    second_half = map(lambda x: insert_bit(x, di, to_bit),  route(c, b, N-1))

    return list(first_half) + list(second_half)


def diff_by_1_bit(N: int, A: int, B: int)->list:
    num_A = num_of_1bit(A)
    num_B = num_of_1bit(B)
    if abs(num_A - num_B) % 2 == 0:
        return []

    return route(A, B, N)


if __name__ == "__main__":
    N, A, B = map(int, input().split())
    ans = diff_by_1_bit(N, A, B)
    if len(ans) == 0:
        print('NO')
    else:
        print('YES')
        print(' '.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
N,A,B=map(int,input().split())
if N==1:
    print('YES')
    print(A,B)
    sys.exit()
C=A^B
C=bin(C)[2:]
num=0
for i in range(len(C)):
    if C[i]=='1':
        num+=1
if num%2==0:
    print('NO')
    sys.exit()
def f(a,b,n):
    if n==1:
        return [a,b]
    for i in range(n):
        if a&(1<<i)!=b&(1<<i):
            break
    x=(((1<<i)-1)&a)+((a>>(i+1))<<i)
    y = (((1 << i) - 1) & b) + ((b >> (i + 1)) << i)

    for z in range(1<<(n)):
        if x!=z and y!=z and bin(x^z).count('1')%2==1 and bin(y^z).count('1')%2==1:
            break
    
    L=f(x,z,n-1)
    M=f(z,y,n-1)
    dp=[0]*(2*len(L))
    num=0
    for l in L:
        dp[num]=(((1<<i)-1)&l)+((l>>i)<<(i+1))+(a&(1<<i))
        num+=1
    for l in M:
        dp[num]=(((1<<i)-1)&l)+((l>>i)<<(i+1))+(b&(1<<i))
        num+=1
    
    return dp

L=f(A,B,N)
print('YES')
print(' '.join(map(str,L)))

Solution (Python):
N, A, B = map(int, input().split())
if bin(A).count("1")%2 == bin(B).count("1")%2:
    print("No")
    exit(0)

print("Yes")

ans = []
def solve(c, A, B, S):
    P = (A ^ B) & S
    b = 1
    if c == 1:
        ans.append(A)
        ans.append(B)
        return
    while not P & b:
        b <<= 1

    S0 = S ^ b
    k = 1
    while not S0 & k:
        k <<= 1
    C = A ^ k
    solve(c-1, A, C, S0)
    solve(c-1, C^b, B, S0)

solve(N, A, B, 2**N-1)
print(*ans)

Solution (Python):
N, A, B = map(int, input().split())
if bin(A).count("1")%2 == bin(B).count("1")%2:
    print("No")
    exit(0)

print("Yes")

ans = []
def solve(c, A, B, S):
    P = A ^ B
    U = P & S
    b = 1
    if c == 1:
        ans.append(A)
        ans.append(B)
        return
    for i in range(N):
        if U & b:
            assert S & b > 0, (P, S, U, b)
            S0 = S ^ b
            k = 1
            while not S0 & k:
                k <<= 1
            C = A ^ k
            solve(c-1, A, C, S0)
            solve(c-1, C^b, B, S0)
            break
        b <<= 1
solve(N, A, B, 2**N-1)
print(*ans)

Solution (Python):
def makep(n, l, mask):
    a = l[0] & mask
    b = l[-1] & mask
    ll = len(l)
    diff = a ^ b
    for i in range(n):
        if(((diff >> i) & 1) != 0):
            diff = 1 << i
            break



    for i, elem in enumerate(l[1:-1], 1):
        if(i < ll // 2):
            l[i] = (l[i] & ~diff) | (a & diff)
        else:
            l[i] = (l[i] & ~diff) | (b & diff)



    nextbit = mask & ~diff
    if(0 != nextbit):
        for i in range(n):
            if(((nextbit >> i) & 1) != 0):
                nextbit = 1 << i
                break
        l[ll // 2 - 1] = (l[ll // 2 - 1] | (a & ~diff)) ^ nextbit
        l[ll // 2 - 0] = (l[ll // 2 - 0] | (a & ~diff)) ^ nextbit



    if(ll > 2):
        l[:ll // 2] = makep(n, l[:ll // 2], mask & ~diff)
        l[ll // 2:] = makep(n, l[ll // 2:], mask & ~diff)
    return(l)

N, A, B = map(int, input().split())

A1num = "{:b}".format(A).count("1")
B1num = "{:b}".format(B).count("1")

if((A1num % 2) == (B1num % 2)):
    print("NO")
    exit()

print("YES")

p = [0] * (2 ** N)
p[0] = A
p[-1] = B
p = makep(N, p, 2 ** N - 1)




print(" ".join(map(str, p)))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def swap_digit(num:int, i:int, j:int):
    if num & (1<<i) and not (num & (1<<j)):
        return num - (1<<i) + (1<<j)
    
    elif not (num & (1<<i)) and num & (1<<j):
        return num + (1<<i) - (1<<j)
    
    else:
        return num
    


def different_digit(n: int, a: int, b: int):
    ret = n-1

    for digit in range(n-1, -1, -1):
        if (a^b) & (1<<digit):
            return digit
        
    return ret


def rec(n: int, a: int, b: int):
    if n == 1:
        return [a,b]
    
    dd = different_digit(n,a,b)
    
    a = swap_digit(a, n-1, dd)
    b = swap_digit(b, n-1, dd)
    na = a & ((1<<(n-1)) - 1)
    nb = b & ((1<<(n-1)) - 1)
    
        
    first = rec(n-1, na, na^1)
    latte = rec(n-1, na^1, nb)

    if a & (1<<(n-1)):
        ret = list(map(lambda x: x + (1<<(n-1)), first)) + latte
    else:
        ret = first + list(map(lambda x: x + (1<<(n-1)), latte))

    return [swap_digit(reti, n-1, dd) for reti in ret]


n,a,b = li()
if bin(a).count('1') % 2 == bin(b).count('1') % 2:
    print("NO")
    
else:
    print("YES")
    print(*rec(n,a,b))

Solution (Python):
import sys

def remove_bit(num, i):
    high = (num >> (i + 1)) << i
    low = num & ((1 << i) - 1)
    return high + low

def insert_bit(num1, num2, i):
    high = num1 >> i << (i + 1)
    low = num1 & (-1 + (1 << i))
    insert = num2 & (1 << i)
    return high + insert + low

def solve(N, A, B):
    if N == 1:
        return [A, B]

    r_bit = -1
    for i in range(N):
        if (A >> i) & 1 != (B >> i) & 1:
            r_bit = i
            break
    if r_bit == -1:
        import pdb; pdb.set_trace()

    AA = remove_bit(A, r_bit)
    BB = remove_bit(B, r_bit)

    C = -1
    for C in range(2**(N-1)):
        if bin(AA ^ C).count('1') % 2 == 1 and  bin(AA ^ C).count('1') % 2 == 1:
            break
    A_list = solve(N - 1, AA, C)
    B_list = solve(N - 1, C, BB)

    A_list = list(map(lambda x: insert_bit(x, A, r_bit), A_list))
    B_list = list(map(lambda x: insert_bit(x, B, r_bit), B_list))

    return A_list + B_list


def main(N, A, B):
    if (bin(A).count('1') + bin(B).count('1')) % 2 == 0:
        print('NO')
        sys.exit()

    print('YES')
    ans_list = solve(N, A, B)

    assert A == ans_list[0]
    assert B == ans_list[-1]
    for i in range(len(ans_list) - 1):
        assert bin(ans_list[i] ^ ans_list[i+1]).count('1') == 1

    for num in ans_list:
        sys.stdout.write('%d '%num)
    print()



if __name__ == '__main__':
    N, A, B = map(int, input().split())
    main(N, A, B)

Solution (Python):






N, A, B = [int(t) for t in input().split()]

def grayCode(n):
    """nビットGrayコードの生成器"""
    for v in range(2 ** n):
        yield v ^ (v >> 1)

def grayCodeEnding(b, n):
    """0で始まりbで終わるnビットGrayコードの生成器"""
    code = list(grayCode(n))
    l = len(code)
    p = code.index(b)  
    assert p % 2 == 1  

    
    q = 0
    while q != p:
        yield code[q]
        if q % 2 == 0:
            q = l - 1 - q
        else:
            q += 1 if q < p else -1

    
    q = l - 1 - q
    d = 1 if q < p else -1
    for i in range(q + d, p + d, d):
        yield code[i]

def weight(v):
    """vをNビット2進表記したときの1の個数"""
    return sum(1 for k in range(N) if (v & (1 << k)) != 0)


B ^= A


if weight(B) % 2 == 0:
    print('NO')
    exit()

print('YES')
code = [A ^ c for c in grayCodeEnding(B, N)]
print(' '.join(str(c) for c in code))