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



Sample input:
2 1 3


Sample output:
YES
1 0 2 3

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    ans = 1
    for i in d.keys():
        ans *= d[i]+1
        ans %= mod
    print(ans-1)
#B
def B():
    n = I()
    c = IR(n)
    v = [[i+1] for i in range(n-1)]
    v.append([])
    d = defaultdict(deque)
    for i in range(n):
        d[c[i]].append(i)
    for i in d.keys():
        x = None
        while d[i]:
            y = d[i].popleft()
            if x != None and y != x+1:
                v[x].append(y)
            x = y
    path = [0]*(n)
    path[0] = 1
    q = [0]
    for x in range(n-1):
        for y in v[x]:
            path[y] += path[x]
            path[y] %= mod
    print(path[-1])
#C
def C():
    def dfs(ans,l,r,d):
        if r != l+1:
            i = n-1
            c = ans[l]^ans[r]
            while not c&po2[i]:i -= 1
            d[i] = 1
            j = 0
            while d[j] or i == j:j += 1;j %= n
            m = (l+r)//2
            ans[m] = ans[l]^po2[j]
            ans[m+1] = ans[m]^po2[i]
            dfs(ans,l,m,d[:i]+[1]+d[i+1:])
            dfs(ans,m+1,r,d[:i]+[1]+d[i+1:])
    n,a,b = LI()
    po2 = [1]*(n+1)
    for i in range(1,n+1):
        po2[i] = po2[i-1]*2
    k = b^a
    c = 0
    bi = []
    i = 0
    g = [0]*n
    while k > 0:
        if k%2:
            bi.append(i)
            g[i] = 1
        c += k%2
        k//= 2
        i += 1
    f = c
    bi = bi[::-1]
    if not f%2:
        print("NO")
        quit()
    ans = [0]*po2[n]
    ans[0] = a
    ans[po2[n]-1] = b
    d = [0]*n
    dfs(ans,0,po2[n]-1,d)
    print("YES")
    print(*ans)
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
n, a, b = map(int, raw_input().split())

def doit(aa, bb, mask):
    bits   = filter(lambda b: mask & (1 << b) == 0, range(n))
    differ = filter(lambda b: (aa ^ bb) & (1 << b), bits)[-1]
    change = filter(lambda b: differ != b, bits)
    if not change:
        return [aa, bb]
    ab = aa ^ (1 << change[0])
    ba = ab ^ (1 << differ)
    return doit(aa, ab, mask | (1 << differ)) + doit(ba, bb, mask | (1 << differ))

if bin(a ^ b).count('1') % 2 != 1:
    print "NO"
else:
    print "YES"
    ret = doit(a, b, 0)
    print " ".join(map(str, ret))

Submission status: Accepted

Solution code:
n, a, b = map(int, raw_input().split())

def doit(a, b, mask):
    differ = -1
    for i in range(n):
        if mask & (1 << i) == 0 and (a ^ b) & (1 << i) != 0:
            differ = i
    same = -1
    for i in range(n):
        if mask & (1 << i) == 0 and i != differ:
            same = i
    if same == -1:
        return [a, b]
    return (doit(a, a ^ (1 << same), mask | (1 << differ)) +
            doit(a ^ (1 << same) ^ (1 << differ), b, mask | (1 << differ)))

if bin(a ^ b).count('1') % 2 != 1:
    print "NO"
else:
    print "YES"
    ret = doit(a, b, 0)
    print " ".join(map(str, ret))

Submission status: Accepted

Solution code:
def split(n, a, b, remain, ai, ans, width, l=None):
    # print(n, a, b, remain, ai, ans, width)
    # print(*(f'{c:5d}' for c in ans))
    # print(*(f'{c:05b}' for c in ans))
    if width == 2:
        ans[ai] = a
        ans[ai + 1] = b
        return
    if l is None:
        x = a ^ b
        y = x & -x  # Rightmost Bit at which is different for a and b
        l = y.bit_length() - 1
    else:
        y = 1 << l
    remain.remove(l)
    i = next(iter(remain))
    lb = a ^ (1 << i)
    ra = lb ^ y
    width >>= 1
    split(n, a, a ^ (1 << i), remain, ai, ans, width, i)
    split(n, ra, b, remain, ai + width, ans, width)
    remain.add(l)


def solve(n, a, b):
    if bin(a).count('1') % 2 == bin(b).count('1') % 2:
        print('NO')
        return
    remain = set(range(n))
    ans = [0] * (1 << n)
    split(n, a, b, remain, 0, ans, 1 << n)
    print('YES')
    print(*ans)


n, a, b = list(map(int, input().split()))
solve(n, a, b)

Submission status: Accepted

Solution code:
def split(n, a, b, remain, ai, ans, width):
    # print(n, a, b, remain, ai, ans, width)
    # print(*(f'{c:5d}' for c in ans))
    # print(*(f'{c:05b}' for c in ans))
    if width == 2:
        ans[ai] = a
        ans[ai + 1] = b
        return
    x = a ^ b
    y = x & -x  # Rightmost Bit at which is different for a and b
    l = y.bit_length() - 1
    remain.remove(l)
    i = next(iter(remain))
    lb = a ^ (1 << i)
    ra = lb ^ y
    width >>= 1
    split(n, a, a ^ (1 << i), remain, ai, ans, width)
    split(n, ra, b, remain, ai + width, ans, width)
    remain.add(l)


def solve(n, a, b):
    if bin(a).count('1') % 2 == bin(b).count('1') % 2:
        print('NO')
        return
    remain = set(range(n))
    ans = [0] * (1 << n)
    split(n, a, b, remain, 0, ans, 1 << n)
    print('YES')
    print(*ans)


n, a, b = list(map(int, input().split()))
solve(n, a, b)

Submission status: Accepted

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


def f(n, a, b):
    if n == 1:
        return [a, b]

    mask = 1 << (n-1)
    if a & mask == b & mask:
        v1 = f(n-1, a, b)
        v2 = f(n-1, a ^ mask, v1[1] ^ mask)
        ret = v1[:1]
        ret.extend(v2)
        ret.extend(v1[1:])
        return ret
    else:
        v1 = f(n-1, a, a ^ 1)
        v2 = f(n-1, a ^ 1 ^ mask, b)
        v1.extend(v2)
        return v1


if bin(A ^ B).count('1') % 2 == 0:
    print("NO")
else:
    print("YES")
    res = f(N, A, B)
    for p in res:
        print(p)

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

DIV = 10**9+7

def make2d_arr(w,h,val =INF):
    return [[val]*w for i in xrange(h)]

def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs

def findMinDiff(N,A,B,checked):
    for i in xrange(N):
        if checked[i]:
            continue
        if ((A ^ B)& (1<<i))!= 0:
            return i
    return -1


def findC(N,A,B,checked):
    #print N,A,B
    now_chk = checked[:]
    m = findMinDiff(N,A,B,checked)
    if m ==-1:
        return [A]
    now_chk[m]= True
    exp_m = 1<<m
    for i in xrange(N):
        if not now_chk[i]:
            exp_i = (1<<i)
            C = A ^ exp_i
            fst = findC(N,A,C, now_chk)
            snd = findC(N,C,B, now_chk)
            snd = map(lambda x: (x&((1<<N)-1-exp_m)) + (B & exp_m),  snd)
            return fst+snd

    else:
        return [A,B]

N,A,B = ints_raw()

DIF_B = []
A2s = []
B2s = []
num_db =0

for i in xrange(N):
    a2 = (A>>i)%2
    b2 = (B>>i)%2
    A2s.append(a2)
    B2s.append(b2)
    if a2 == b2:
        DIF_B.append(0)    
    else:
        DIF_B.append(1)
        num_db+=1
    
numP = (2**N)-1
if (num_db > numP) or (num_db%2 ==0):
    print "NO"
else:
    print "YES"
    ans =  findC(N,A,B,[False]*N)
    for a in ans:
        print a,

Submission status: Accepted

Solution code:
def bit_remove(x,bit):
    return ((x>>(bit+1))<<bit)+(x%(1<<bit))
def bit_insert(x,bit,i):
    return ((x>>bit)<<(bit+1))+(i<<bit)+(x%(1<<bit))

def solve(n,a,b):
    if n==1:
        return [a,b]
    for bit in range(n):
        if (a^b)&(1<<bit):
            break
    c,d=bit_remove(a,bit),bit_remove(b,bit)
    L=list(map(lambda x: bit_insert(x,bit,(a>>bit)&1),solve(n-1,c,c^1)))
    R=list(map(lambda x: bit_insert(x,bit,(b>>bit)&1),solve(n-1,c^1,d)))
    return L+R

n,a,b=map(int,input().split())
if not bin(a^b).count('1')%2:
    print('NO')
else:
    print('YES')
    print(*solve(n,a,b))

Submission status: Accepted

Solution code:
def rm_bit(n, i):
    return n // (2**(i+1)) * (2**i) + (n % (2**i))


def ins_bit(n, i, b):
    return n // (2**i) * (2**(i+1)) + (n % (2**i)) + b * (2**i)


def solve(N, A, B):
    if N == 1:
        return [A, B]
    idx = -1
    for i in range(N):
        if (A ^ B) & (2**i):
            idx = i
            break
    ra = rm_bit(A, idx)
    rb = rm_bit(B, idx)
    a = list(map(lambda x: ins_bit(x, idx, (A >> idx) & 1), solve(N-1, ra, ra ^ 1)))
    b = list(map(lambda x: ins_bit(x, idx, (B >> idx) & 1), solve(N-1, ra ^ 1, rb)))
    return a + b


def main():
    N, A, B = map(int, input().split())
    x = A ^ B
    cnt = 0
    for i in range(N):
        if x & (2**i):
            cnt += 1
    if cnt % 2 == 0:
        print("NO")
    else:
        print("YES")
        print(*solve(N, A, B))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def i_to_b(n, N):
    A = [0] * N
    for i in range(N):
        A[i] = (n // 2**i) % 2
    return A


def b_to_i(A):
    ret = 0
    for i in range(len(A)):
        ret += i**2*A[i]
    return ret


def rm_bit(n, i):
    return n // (2**(i+1)) * (2**i) + (n % (2**i))


def ins_bit(n, i, b):
    return n // (2**i) * (2**(i+1)) + (n % (2**i)) + b * (2**i)


def solve(N, A, B):
    if N == 1:
        return [A, B]
    idx = -1
    for i in range(N):
        if (A ^ B) & (2**i):
            idx = i
            break
    ra = rm_bit(A, idx)
    rb = rm_bit(B, idx)
    a = list(map(lambda x: ins_bit(x, idx, (A >> idx) & 1), solve(N-1, ra, ra ^ 1)))
    b = list(map(lambda x: ins_bit(x, idx, (B >> idx) & 1), solve(N-1, ra ^ 1, rb)))
    return a + b


def main():
    N, A, B = map(int, input().split())
    binA = i_to_b(A, N)
    binB = i_to_b(B, N)
    if abs(sum(binA) - sum(binB)) % 2 == 0:
        print("NO")
        return
    print("YES")
    print(*solve(N, A, B))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dc(n):
    return sum(map(int, list(bin(n)[2:])))
def calc(a, b, X):
    if len(X) == 1:
        return [a, b]
    i = 0
    while i not in X or (a & (1<<i)) == (b & (1<<i)):
        i += 1
    j = X[1] if i == X[0] else X[0]
    Y = [x for x in X if x != i]
    return calc(a, a ^ (1<<j), Y) + calc(a ^ (1<<j) ^ (1<<i), b, Y)

N, A, B = map(int, input().split())
if dc(A^B) % 2 == 0:
    print("NO")
else:
    print("YES")
    print(*calc(A, B, list(range(N))))

Submission status: Accepted

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

# AとBの違うビットが偶数個なら不可能
if bin(A ^ B).count('1') % 2 == 0:
  print('NO')
  exit()

print('YES')
visited = set([A])
now = A
targets = [[B, set([2**i for i in range(N)])]]
print(now)
while True:
  if now == B:
    break
  target, bits = targets[-1]
  # nowとtargetで異なるビットを見つけ、
  # 異なるビットを変えない空間上で適当に1ビット変えた所をtargetに積む
  xor = now ^ target
  flag = False
  for i in bits:
    if xor & i:
      for j in bits:
        if j != i and now ^ j not in visited:
          targets.append([now ^ j ^ i, {j}])
          targets.append([now ^ j, bits - {i}])
          flag = True
          break
      if flag:
        break
  else:
    # 最大限遠回りしているはずなので、動く
    now = target
    visited.add(now)
    targets.pop()
    print(now)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
AB = A ^ B
D = bin(AB)[2:].count('1')
if D % 2 == 0:
  print('NO')
else:
  print('YES')
  C = [0] * (2 ** N)
  C[0] = str(A)
  P = []
  for i in range(N):
    if AB % 2:
      P = P + [i]
    else:
      P = [i] + P
    AB >>= 1
  for i in range(1, 2 ** N):
    k = 0
    b = i
    while b % 2 == 0:
      k += 1
      b >>= 1
    A ^= 1 << P[k]
    C[i] = str(A)
  k = 0
  for i in range(D // 2):
    k += 1 / (4 ** (i + 1))
    K = int(2 ** N * (1 - k))
    C = C[:K-1] + C[K+1:] + C[K-1:K+1][::-1]
  print(' '.join(C))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, A, B = LI()
    X = A ^ B
    if bin(X).count('1') % 2 == 0:
        print('No')
        return 0
    print('Yes')
    # 入れ替えなきゃいけない桁
    m = []
    s = []
    for i in range(N):
        if (X // (2 ** i)) % 2:
            m.append(i)
        else:
            s.append(i)
    ans = [0] * (2 ** N)
    def get(se, ms):
        if len(ms) > 2:
            return get(ms[1:2] + se, ms[2:]) + ms[0:1] + get(ms[2:] + se, ms[1:2])
        elif len(ms) == 1:
            return get(se, []) + ms[0:1] + get(se, [])
        if len(se) == 0:
            return []
        return get(se[1:], []) + se[0:1] + get(se[1:], [])
    swap = get(s, m)
    ans = [A]
    for sw in swap:
        ans.append(ans[-1] ^ (2 ** sw))
    print(*ans)

    return 0

main()

Submission status: Accepted

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

# AとBの違うビットが偶数個なら不可能
if bin(A ^ B).count('1') % 2 == 0:
  print('NO')
  exit()

print('YES')
visited = set([A])
n = 1
now = A
xbits = set([2**i for i in range(N)])
is_neighbor = lambda a, b: (a ^ b) in xbits
targets = [(B, xbits)]
M = 2 ** N - 1
print(now)
while True:
  if now == B:
    break
  target, bits = targets[-1]
  # 異なるビットを見つけ、
  # そのビット以外で、適当に1ビット変えた所を暫定targetにする
  xor = now ^ target
  flag = False
  for i in bits:
    if xor & i:
      for j in bits:
        if j != i and now ^ j not in visited:
          targets.append((now ^ j ^ i, {j}))
          targets.append((now ^ j, bits - {i}))
          flag = True
          break
      if flag:
        break
  else:
    # 多分隣り合っている
    now = target
    visited.add(now)
    n += 1
    print(now)
    targets.pop()

Submission status: Accepted

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

ans = []


def f(s, d):
    if bin(d).count('1') == 1:
        ans.append(s)
        ans.append(s ^ d)
        return
    else:
        if (s & ~d == B & ~d) and ((s & d) ^ (B & d) != ((1 << N) - 1)):
            d1 = d - (1 << next(i for i in range(N) if s & (1 << i) != B & (1 << i)))
        else:
            d1 = d - (1 << next(i for i in range(N) if (d >> i) & 1))
        # print(s, d, d1)
        f(s, d1)
        t = ans[-1] ^ (d ^ d1)
        d2 = d - (d ^ d1)
        f(t, d2)
        return


if sum((A & (1 << i)) != (B & (1 << i)) for i in range(N)) % 2 == 0:
    print('NO')
else:
    print('YES')
    f(A, ((1 << N) - 1))
    print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
def solve():
    N, A, B = map(int, input().split())
    X = A ^ B
    #print(X)
    x = X
    s = 0
    while x > 0:
        s += x % 2
        x //= 2
    #print(s)
    if s % 2 == 0:
        print("NO")
        return
    print("YES")
    g = []
    for i in range(2 ** N):
        g.append(i ^ (i >> 1))
    #print(g)
    i = 0
    while True:
        print(g[i] ^ A, end = " ")
        if i % 2 == 0:
            j = 2 ** N - 1 - i
        elif j < 2 ** (N - 1):
            j += 1
        else:
            j -= 1
        if g[j] == X:
            break
        i = j
    if i < 2 ** (N - 1):
        for k in range(i + 1, j + 1):
            print(g[k] ^ A, end = " ")
    else:
        for k in range(i - 1, j - 1, -1):
            print(g[k] ^ A, end = " ")
    return
        
solve()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

M = 10 ** 9 + 7

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def bitcount(a, N):
  return sum((a & (1 << i)) > 0 for i in range(N))

def topbit(a, N):
  return next(i for i in range(N-1, -1, -1) if (a & (1 << i)) > 0)

def swap(x, i, j):
  y = x & ~(1 << i) & ~(1 << j)
  if (x & (1 << i)) > 0:
    y |= 1 << j
  if (x & (1 << j)) > 0:
    y |= 1 << i
  return y

def solve(N, A, B):
  if N == 1:
    ans = [A & 1, B & 1]
    return ans
  C = A ^ B
  t = topbit(C, N)
  AA = swap(A, t, N-1)
  BB = swap(B, t, N-1)
  D = AA ^ 1
  ans = []
  if B & (1 << t) > 0:
    ans.extend(swap(x, t, N-1) for x in solve(N-1, AA, D))
    ans.extend(swap(x, t, N-1) | (1 << t) for x in solve(N-1, D, BB))
  else:
    ans.extend(swap(x, t, N-1) | (1 << t)for x in solve(N-1, AA, D))
    ans.extend(swap(x, t, N-1) for x in solve(N-1, D, BB))
  return ans

N, A, B = reads()
if bitcount(A ^ B, N) % 2 == 0:
  print("NO"); exit()
print("YES")
print(*solve(N, A, B))

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
C=[]
D=[]
tmp=1
for i in range(N):
    if A^tmp>A:
        C.append(0)
    else:
        C.append(1)
    if B^tmp>B:
        D.append(0)
    else:
        D.append(1)
    tmp=tmp*2
X=[];Y=[]
S=0
T=0
for i in range(N):
    if C[i]==D[i]:
        X.append(i)
        if C[i]==1:
            S+=2**i
    else:
        Y.append(i)
        if C[i]==1:
            T+=2**i
#print(X,Y)
if len(Y)%2==0:
    print("NO")
    exit()
def xadd(Lst,k):
    Res=[]
    for i in Lst:
        Res.append(i)
    for i in Lst[::-1]:
        Res.append(i+2**k)
    return Res
XL=[0]
if len(X)!=0:
    XL.append(2**X[0])
for i in range(1,len(X)):
    XL=xadd(XL,X[i])
XL=[i^S for i in XL]
YL=[0,2**Y[0]]
def yadd2(Lst,k1,k2):
    Res=[]
    for i in range(len(Lst)-1):
        if i%2==0:
            Res.append(Lst[i]+0*2**k1+0*2**k2)
            Res.append(Lst[i]+0*2**k1+1*2**k2)
            Res.append(Lst[i]+1*2**k1+1*2**k2)
            Res.append(Lst[i]+1*2**k1+0*2**k2)
        else:
            Res.append(Lst[i]+1*2**k1+0*2**k2)
            Res.append(Lst[i]+1*2**k1+1*2**k2)
            Res.append(Lst[i]+0*2**k1+1*2**k2)
            Res.append(Lst[i]+0*2**k1+0*2**k2)
    Res.append(Lst[-1]+1*2**k1+0*2**k2)
    Res.append(Lst[-1]+0*2**k1+0*2**k2)
    Res.append(Lst[-1]+0*2**k1+1*2**k2)
    Res.append(Lst[-1]+1*2**k1+1*2**k2)
    return Res
for i in range(len(Y)//2):
    YL=yadd2(YL,Y[-1-2*i],Y[-2-2*i])
YL=[i^T for i in YL]
#print(YL)
ans=[]
for i in range(len(YL)):
    for j in range(len(XL)):
        if i%2==0:
            ans.append(YL[i]+XL[j])
        else:
            ans.append(YL[i]+XL[-j-1])
print("YES")
print(" ".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
def split(n, a, b, used, ai, ans, width):
    # print(n, a, b, used, ai, ans, width)
    # print(*(f'{c:5d}' for c in ans))
    # print(*(f'{c:05b}' for c in ans))
    if width == 2:
        ans[ai] = a
        ans[ai + 1] = b
        return
    x = a ^ b
    y = x & -x  # Rightmost Bit where is different a and b
    l = y.bit_length() - 1
    used.append(l)
    i = 0
    for i in range(n):
        if i not in used:
            break
    la, lb = a, a ^ (1 << i)
    ra, rb = lb ^ y, b
    width >>= 1
    split(n, la, lb, used, ai, ans, width)
    split(n, ra, rb, used, ai + width, ans, width)
    used.pop()


def solve(n, a, b):
    if bin(a).count('1') % 2 == bin(b).count('1') % 2:
        print('NO')
        return
    used = []
    ans = [0] * (1 << n)
    split(n, a, b, used, 0, ans, 1 << n)
    print('YES')
    print(*ans)


n, a, b = list(map(int, input().split()))
solve(n, a, b)

Submission status: Runtime Error

Solution code:
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)
    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)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
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 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)
    mid=aa[0]
    if mid^1<<k==b:mid=aa[1]
    return solve(aa,a,mid)+solve(bb,mid^1<<k,b)

def main():
    popcnt=lambda x:bin(x).count("1")

    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()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
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 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)
    mid=aa[0]
    if mid^1<<k==b:mid=aa[1]
    return solve(aa,a,mid)+solve(bb,mid^1<<k,b)

def main():
    popcnt=lambda x:bin(x).count("1")

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

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

main()

Submission status: Runtime Error

Solution code:
n,a,b = map(int,input().split())
for i in range(n):
  if a^b == 1<<i:
    break
else:
  print("NO")
  exit()
st = min(a,b)
bt = (a^b).bit_length()-1
def change(x):
  x ^= st
  if ((x>>bt)&1) ^ ((x>>(n-1))&1):
    x ^= (1<<bt)+(1<<(n-1))
  return x
if n == 1:
  print("YES")
  print(a,b)
  exit()
ls = [0]
x = 0
cnt = 1
while x != 1<<(n-1):
  cntc = cnt
  divcnt = 0
  while cntc%2 == 0:
    cntc //= 2
    divcnt += 1
  x ^= 1<<divcnt
  ls.append(x)
  cnt += 1
print("YES")
ansls = [change(ls[i]) for i in range(2**n)]
print(2/0)
if a < b:
  print(*ansls)
else:
  print(*ansls[::-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n, a, b = map(int, input().split())
ba = f"{a:020b}"[::-1]
bb = f"{b:020b}"[::-1]
d = [False] * 20
for i in range(20):
    if ba[i] != bb[i]:
        d[i] = True
bn = (1 << n) - 1
sd = sum(d)
if sd % 2 == 0 or sd > bn - 1:
    print("NO")
    exit()
print("YES")
print(a, end="")
for k in range(bn):
    if k < sd:
        for i in range(20):
            if d[i]:
                d[i] = False
                a = a ^ (1 << i)
                print("", a, end="")
                break
    else:
        a ^= 1
        print("", a, end="")
print("")

Submission status: Runtime Error

Solution code:

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

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

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

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ
"""
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 N >= 6:
    print (X)

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 (format(A,"b").zfill(N))

#print (ans[-1])
print (" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:

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

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

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

根本的に違う？
→最初と最後のハミング距離が1以外も可能？
→いやー無理やろ
"""
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 N >= 4:
    print (X)

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 (format(A,"b").zfill(N))

#print (ans[-1])
print (" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import os
import sys

from scipy.misc import comb

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

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


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


# 距離が1だけ変わる
# 2^N 回移動して A から B の距離にたどり着けるか


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


counts = []
for i in range(N + 1):
    counts.append(comb(N, i, exact=True))
dist_hist = []
# 反対側まで行く
for d in range(dist(A ^ B), N + 1):
    counts[d] -= 1
    dist_hist.append(d)
# 距離ゼロまで戻ってこれるか
for i in reversed(range(1, N + 1)):
    if counts[i] < 0:
        break
    for _ in range(counts[i]):
        dist_hist.append(i - 1)
        dist_hist.append(i)
    dist_hist.append(i - 1)
    counts[i - 1] -= counts[i] + 1
    counts[i] = 0

# 戻ってこれなかった
if len(dist_hist) != (1 << N):
    print('NO')
    exit()
dist_hist.reverse()

# 次数の多い頂点に行けば OK
vertices = [[] for _ in range(N + 1)]
# 次数は常に N
dims = [N] * (1 << N)
for v in range(1 << N):
    vertices[dist(v)].append(v)

v_hist = [0]
v = 0
for d, nd in zip(dist_hist, dist_hist[1:]):
    max_dim = 0
    next_v = None
    for i in range(N):
        nv = v ^ (1 << i)
        if d < nd and v < nv or d > nd and v > nv:
            if dims[nv] > max_dim:
                max_dim = dims[nv]
                next_v = nv
        dims[v ^ (1 << i)] -= 1
    dims[v] = 0
    v = next_v
    v_hist.append(v)

# v_hist[0] -> v_hist[-1] に行ける
# v_hist[-1] が A^B になるように入れ替える
from_i = []
to_i = []
for i in range(N):
    if v_hist[-1] ^ (1 << i):
        from_i.append(i)
    if A ^ B ^ (1 << i):
        to_i.append(i)
for i in range(N):
    if v_hist[-1] ^ (1 << i) == 0:
        from_i.append(i)
    if A ^ B ^ (1 << i) == 0:
        to_i.append(i)

ans = []
for v in v_hist:
    a = 0
    for i in range(N):
        a += (v >> from_i[i] & 1) << to_i[i]
    ans.append(a ^ A)
print('YES')
print(*ans)

Submission status: Runtime Error

Solution code:
print(NO)

Submission status: Runtime Error

Solution code:
def gray_code(n):
    return n ^ (n >> 1)

n, a, b = map(int, input().split())
gray_list = []
for i in range(0, 2**n):
    gray_list.append(gray_code(i))

for i in range(n):
    if gray_list[i] == a:
        ai = i

gray_list = gray_list[ai:] + gray_list[0:ai]

for i in range(n):
    if gray_list[i] == b:
        bi = i

if bin(gray_list[bi-1] ^ gray_list[-1]).count("1") != 1:
    print("No")
else:
    print("Yes")
    gray_list = gray_list[0:bi] + gray_list[bi:][::-1]
    print(" ".join(map(str, gray_list)))

Submission status: Runtime Error

Solution code:
n,a,b = map(int,input().split())
l = [False for i in range(2**n)]
def dfs(x,y,fl,ans):
    globals()
    if False in fl:
        for i in range(n):
            if 0<=x+2**i<2**n and fl[x+2**i]==False:
                fl[x + 2 ** i]=True
                dfs(x+2**i,y,fl,ans+[x+2**i])
                fl[x + 2 ** i] = False
            if 0<=x-2**i<2**n and fl[x-2**i]==False:
                fl[x - 2 ** i] = True
                dfs(x-2**i,y,fl,ans+[x-2**i])
                fl[x - 2 ** i] = False
        return
    else:
        if x!=y:
            return
        for i in ans:
            print(i,end=' ')
        print('')
        exit()
if (bin(a).count('1')-bin(b).count('1'))%2==0:
    print('NO')
else:
    print('YES')
    l[a]=True
    dfs(a,b,l,[a,])

Submission status: Runtime Error

Solution code:
import numpy as np
n,a,b = list(map(int,input().split()))
c = a^b
bit = 2**np.array(list(range(0,n)))
bit = list(bit)
point = list(range(0,2**n))
point.remove(a)
point.remove(b)
way = list()
way.append(a)
ans = "NO"
for i in range(0,n):
    if(c in bit):
        ans = "YES"
        break
if ans == "YES":
    for i in range(0,2**n-2):
        if point == []:
            break
        else:
            for k in point:
                if (way[i]^k in bit):
                    way.append(k)
                    point.remove(k)
                    break
print(ans)
if ans == "YES":
    way.append(b)
    print(*way)