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: Time Limit Exceeded

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]
    while q:
        x = heappop(q)
        for y in v[x]:
            if path[y] == 0:
                heappush(q,y)
            path[y] += path[x]
            path[y] %= mod
    print(path[-1])
#C
def C():
    sys.setrecursionlimit(100000)
    n,a,b = LI()
    def dfs(l,q,f):
        if len(l) == po2[n]:
            if l[-1] == b:
                print("YES")
                print(*l)
                quit()
        x = l[-1]
        m = -1
        k = -1
        for i in po2[:-1]:
            y = x^i
            if f[y] > m:
                m = f[y]
                k = y
        if m != -1:
            for i in po2[:-1]:
                y = x^i
                if f[y] == m:
                    q.append(y)
            for y in q:
                dfs(l+[y],[],f[:y]+[-1]+f[y+1:])
    po2 = [1]*(n+1)
    for i in range(1,n+1):
        po2[i] = po2[i-1]*2
    ans = [a]
    f = [0]*po2[n]
    for i in range(po2[n]):
        k = b^i
        c = 0
        while k > 0:
            c += k%2
            k//= 2
        f[i] = c
    if not f[a] in [1,3,5,7,9,11,13,15,17,19]:
        print("NO")
        quit()
    f[a] = -1
    l = [a]
    dfs(l,[],f)
    print("NO")
#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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def rec(v, mask):
    global ans
    mask |= 1 << v
    # print(v, bin(mask)[2:].zfill(2 ** N), ans[::-1], mask, (1 << (1 << N)) - 1)
    if mask == (1 << (1 << N)) - 1:
        if v == B:
            ans.append(v)
            return True
        else:
            return False

    chk = 0
    for nnv in g[B]:
        if nnv == v: continue
        chk += (mask >> nnv) & 1
    if chk == N:
        return False

    for nv in g[v]:
        if (mask >> nv) & 1 == 1: continue
        if rec(nv, mask):
            ans.append(v)
            return True
    return False


N, A, B = map(int, input().split())
g = [[] for _ in range(1 << N)]

for i in range(1 << N):
    for j in range(N):
        g[i].append(i & ~(1 << j) | ~i & (1 << j))
        # 隣接可能な値

ans = []
rec(A, 0)

# print(ans)
if ans:
    print('YES')
    ans = ans[::-1]
    print(*ans)
else:
    print('NO')

Submission status: Time Limit Exceeded

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]
    while q:
        x = heappop(q)
        for y in v[x]:
            if path[y] == 0:
                heappush(q,y)
            path[y] += path[x]
            path[y] %= mod
    print(path[-1])
#C
def C():
    sys.setrecursionlimit(100000)
    n,a,b = LI()
    def dfs(l,q,f):
        if len(l) == po2[n]:
            if l[-1] == b:
                print("YES")
                print(*l)
                quit()
        x = l[-1]
        m = -1
        k = -1
        for i in po2[:-1]:
            y = x^i
            if f[y] > m:
                m = f[y]
                k = y
        if m != -1:
            for i in po2[:-1]:
                y = x^i
                if f[y] == m:
                    q.append(y)
            for y in q:
                dfs(l+[y],[],f[:y]+[-1]+f[y+1:])
    po2 = [1]*(n+1)
    for i in range(1,n+1):
        po2[i] = po2[i-1]*2
    ans = [a]
    f = [0]*po2[n]
    for i in range(po2[n]):
        k = b^i
        c = 0
        while k > 0:
            c += k%2
            k//= 2
        f[i] = c
    f[a] = -1
    l = [a]
    dfs(l,[],f)
    print("NO")
#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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def rec(v, mask):
    global ans
    mask |= 1 << v
    # print(v, bin(mask)[2:].zfill(2 ** N), ans[::-1], mask, (1 << (1 << N)) - 1)
    if mask == (1 << (1 << N)) - 1:
        if v == B:
            ans.append(v)
            return True
        else:
            return False

    for nv in g[v]:
        if (mask >> nv) & 1 == 1: continue
        if rec(nv, mask):
            ans.append(v)
            return True


N, A, B = map(int, input().split())
g = [[] for _ in range(1 << N)]

for i in range(1 << N):
    for j in range(N):
        g[i].append(i & ~(1 << j) | ~i & (1 << j))
        # 隣接可能な値

ans = []
rec(A, 0)

# print(ans)
if ans:
    print('YES')
    ans = ans[::-1]
    print(*ans)
else:
    print('NO')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
    #print(bit(xx),a,b,k,bit(aa),bit(bb),format(mid,"b"))
    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()

Submission status: Accepted

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

Submission status: Accepted

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

# a -> bにする手順 (制約なし)
def solve(n, a, b):
    c = a ^ b
    # 0 -> a ^ b, popcnt(c)は奇数である必要がある
    if popcnt(c) % 2 == 0:
        print('NO')
        exit(0)
    return [i ^ a for i in solve2(n, c)]

# 0 -> cにする手順 (c: popcntは奇数)
def solve2(n, c):
    c_1 = popcnt(c)
    d = (1 << c_1) - 1  # 0..01..1
    ret_d = solve3(n, d, c_1)
    ret_c = move(ret_d, n, d, c)
    return ret_c

# 0 -> dにする手順 (d: 0..01..1)
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

# 0 -> (1<<n)-1 にする手順 (d: 1..1)
def solve4(n):
    if n == 1:
        return [0, 1]
    # 0 + 0 * (n - 1) -> 0 + 1 + 0 * (n - 2)
    # 1 + 1 + 0 * (n - 2) -> 1 + 1 * (n - 1) : 再帰的に
    ret = graycode(n - 1) + [(1 << (n - 1)) | i for i in solve(n - 1, 1 << n - 2, mask(n - 1))]
    return ret

# nビットのグレイコード
def graycode(n):
    ret = []
    for i in range(1 << n):
        ret.append(i ^ (i >> 1))
    return ret

# bitの移し換え 001111 -> 011011
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

# aとbを繋げる
def merge(a, b, margin):
    return (a << margin) + b

# nビットのマスク
def mask(n):
    return (1 << n) - 1

n,a,b = map(int,input().split())
res = solve(n, a, b)
print('YES')
print(*res)
# for i in res:
#     print(bin(2 ** n + i)[3:])
# print("len :", len(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

"""
ハミング距離がちょうど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):

    #異なるbitかつ未使用を見つけよう
    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

    #もう一つ未使用bitを見つけよう→見つからなかった時の処理も書く

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

#print (format(A,"b").zfill(N))
#print (format(B,"b").zfill(N))

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




#WA解答2 貪欲で構成しようとしてみてだめだった
"""
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 = []
#print (lis)
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)))
"""

#WA解答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 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: Accepted

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

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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


# 解説
# 違うbitの数が奇数なら戻ってこれる


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


# vs = []
# for i in range(1 << N):
#     for j in range(i, 1 << N):
#         if bitcount(i ^ j) == 1:
#             vs.append((i, j))
# plot_graph(vs)


# @lru_cache(maxsize=None)
# @debug
def solve(n, a, b):
    if n <= 0:
        return []
    if bitcount(a ^ b) % 2 == 0:
        return []
    if n == 1:
        return [a, b]
    # 奇数
    # 違うbitを1つ取り除く
    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')

# for A in range(1 << N):
#     for B in range(1 << N):
#         ans = solve(N, A, B)
#         if ans:
#             assert ans[0] == A
#             assert ans[-1] == B
#             for a, b in zip(ans, ans[1:]):
#                 assert bitcount(a ^ b) == 1
#                 assert a < (1 << N)

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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


# 解説
# 違うbitの数が奇数なら戻ってこれる


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


# vs = []
# for i in range(1 << N):
#     for j in range(i, 1 << N):
#         if bitcount(i ^ j) == 1:
#             vs.append((i, j))
# plot_graph(vs)


# @lru_cache(maxsize=None)
# @debug
def solve(n, a, b):
    if n <= 0:
        return []
    if bitcount(a ^ b) % 2 == 0:
        return []
    if n == 1:
        return [a, b]
    # 奇数
    # 違うbitを1つ取り除く
    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')

# for A in range(1 << N):
#     for B in range(1 << N):
#         ans = solve(N, A, B)
#         if ans:
#             assert ans[0] == A
#             assert ans[-1] == B
#             for a, b in zip(ans, ans[1:]):
#                 assert bitcount(a ^ b) == 1
#                 assert a < (1 << N)

Submission status: Accepted

Solution code:
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)))
# for i in range(pow(2, n) - 1):
#    print(ans[i + 1] - ans[i], end=' ')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
    #print(*[format(a,"b").zfill(n) for a in ans])

main()

Submission status: Accepted

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

Submission status: Accepted

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