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

Submission status: Accepted

Solution code:
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
    #print(i,a,b,x,y,z)
    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
    #print(L,M,dp,i,a,b,x,y,z)
    return dp

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#    print("a = {}, b = {}, mask = {}, ll = {}, diff = {}".format(a, b, mask, ll, diff))

    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)

#    print("l = {}".format(l))

    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

#        print("nextbit = {}, ll//2 = {}, l = {}".format(nextbit, ll//2, l))

    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)

#for i in p:
#    print("{:08b}".format(i))

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

Submission status: Accepted

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

# i-bit目とj-bit目を入れ替える
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
    

# 2つの数のbitが異なる桁を特定する
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

# 上位bitから再帰的に決める
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# AtCoder Grand Contest 031
# Problem C: Differ by 1 Bit

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)  # bの出現位置
    assert p % 2 == 1  # bの重みは奇数なので奇数番目に現れる

    # 両端から交互にyield
    q = 0
    while q != p:
        yield code[q]
        if q % 2 == 0:
            q = l - 1 - q
        else:
            q += 1 if q < p else -1

    # 残りを線形にyield
    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)

# 0 からB ^ A への系列を求めるのと本質的に同じ.
B ^= A

# Bの重みが偶数なら, 長さ 2 ** N の系列は存在しない.
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def trace(bits, idx, history):
  if idx == len(bits):
    history.append(bits[:])
  elif idx == len(bits) - 1:
    history.append(bits[:])
    bits[idx] = 1 - bits[idx]
    history.append(bits[:])
  else:
    trace(bits, idx + 1, history)
    bits[idx] = 1 - bits[idx]
    trace(bits, idx + 1, history)


def down(bits, idx, count, history):
  if idx == len(bits):
    history.append(bits[:])
  elif idx == len(bits) - 1:
    history.append(bits[:])
    bits[idx] = 1 - bits[idx]
    history.append(bits[:])
  elif count > 0:
    trace(bits, idx + 2, history)
    bits[idx] = 1 - bits[idx]
    trace(bits, idx + 2, history)
    bits[idx + 1] = 1 - bits[idx + 1]
    trace(bits, idx + 2, history)
    bits[idx] = 1 - bits[idx]
    down(bits, idx + 2, count - 2, history)
  else:
    trace(bits, idx + 2, history)
    bits[idx + 1] = 1 - bits[idx + 1]
    trace(bits, idx + 2, history)
    bits[idx ] = 1 - bits[idx ]
    trace(bits, idx + 2, history)
    bits[idx + 1] = 1 - bits[idx + 1]
    down(bits, idx + 2, count - 2, history)


def main():
  n, a, b = map(int, input().split())
  x = a ^ b
  count = 0
  remain = 0
  mapper = [-1] * n

  for i in range(n):
    if (x >> i) & 0x1 != 0:
      mapper[count] = i
      count += 1
    else:
      remain += 1
      mapper[-remain] = i

  if count % 2 == 0:
    print('NO', flush=True)
    return

  bits = [0] * n
  history = []
  trace(bits, 1, history)
  bits[0] = 1
  down(bits, 1, count - 1, history)

  for i in range(len(history)):
    v = history[i][:]

    for j, m in enumerate(mapper):
      history[i][n - m - 1] = v[j]

  history = [str(a ^ int(''.join(str(v) for v in h), 2)) for h in history]

  print('YES', flush=True)
  print(' '.join(history), flush=True)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

def sum_digits(n,m):
   r = 0
   while n:
       r, n = r + n % m, n // m
   return r


n,a,b = [int(i) for i in input().split()]

c=a^b
if sum_digits(c,2)%2 == 0:
   print('NO') 
   sys.exit()

def grey(n):
    if n == 1: return [0,1]
    a0 = grey(n-1)
    a2= [(2**(n-2))^i^(2**(n-1)) for i in grey(n-1)] 
    return a0 + a2
    #print(grey(4))

def newgrey(a,b,move):
    if len(move) == 1:
        return [a,b]
    diff = 0
    for j in move:
        if a&(2**j) != b&(2**j):
            diff=j
            break
    ac = a
    bc = b
    for j in move:
        if j == diff: continue
        ac = a^(2**j)
        bc = ac ^ (2**diff)
        if bc != b: break
    return newgrey(a,ac, move-set({diff})) + newgrey(bc,b, move-set({diff}))
    
print('YES')
ans =newgrey(a,b,set(range(n)))
print(*ans)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
M = 2**(N-1)

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

gray = [0]
for i in range(1,M):
    gray.append(gray[-1] ^ (i&(-i)))
grid = [gray, [a+M for a in gray]]

for i,row in enumerate(grid):
    if A in row:
        sx,sy = row.index(A),i
    if B in row:
        gx,gy = row.index(B),i

if (abs(sx-gx) + abs(sy-gy)) % 2:
    print('YES')
else:
    print('NO')
    exit()

ans = [A]

x,y = sx,sy
while (gx-x)%M != 1:
    x += 1
    x %= M
    ans.append(grid[y][x])
y = 1-y
ans.append(grid[y][x])
while x != sx:
    x -= 1
    x %= M
    ans.append(grid[y][x])

if x != gx:
    while 1:
        x -= 1
        x %= M
        ans.append(grid[y][x])
        y = 1-y
        ans.append(grid[y][x])
        if x==gx: break

print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def func(A, B, bit_len):
    if bit_len == 1:
        return [A, B]
    X = A ^ B
    for i in range(bit_len):
        if (X >> i) & 0x01 >= 1:
            break
    del_bit = i
    A_prime = ((A >> (del_bit + 1)) << del_bit) + (A & ((2 ** del_bit) - 1))
    B_prime = ((B >> (del_bit + 1)) << del_bit) + (B & ((2 ** del_bit) - 1))
    C = A_prime ^ 0x01
    retA = func(A_prime, C, bit_len - 1)
    retB = func(C, B_prime, bit_len - 1)
    ret = [0 for i in range(len(retA) + len(retB))]
    for i in range(len(retA)):
        ret[i] = (retA[i] & ((2 ** del_bit) - 1)) + (A & (2 ** del_bit)) + ((retA[i] & (~((2 ** del_bit) - 1))) << 1)
    for i in range(len(retB)):
        ret[len(retA) + i] = (retB[i] & ((2 ** del_bit) - 1)) + (B & (2 ** del_bit)) + ((retB[i] & (~((2 ** del_bit) - 1))) << 1)

    return ret




def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B] = [int(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    countA = 0
    countB = 0
    for i in range(N):
        countA += (A >> i) & 0x01
    for i in range(N):
        countB += (B >> i) & 0x01
    if countA % 2 == countB % 2:
        print "NO"
        return
    ret = func(A, B, N)
    print "YES"
    for i in range(len(ret)):
        print ret[i],
    print

##    data_list = [0 for i in range(2 ** N)]
##    data_list[0] = A
##    pre_i = 0L
##    X = A
##    gray = [v ^ (v >> 1L) for v  in range(2 ** N)]
##    print gray
##
##    B_idx = 0
##    already = set([X])
##    for i in range(1L, 2L**N):
##        X = X ^ ((gray[i] ^ gray[i-1]))
##        if X in already:
##            print "NO"
##            return
##        already.add(X)
##        data_list[i] = X
##        if X== B:
##            B_idx = i
##    Z = data_list[B_idx - 1] ^ data_list[2 ** N - 1]
##
##    count = 0
##    for i in range(N + 1):
##        count += (Z >> i) & 0x01
##    if count != 1:
##        Z = data_list[B_idx - 1] ^ data_list[2 ** N - 3]
##        count2 = 0
##        for i in range(N + 1):
##            count2 += (Z >> i) & 0x01
##        if count2 != 1:
##            print "NO"
##            return
##        else:
##            tmp = data_list[2 ** N - 3]
##            data_list[2 ** N - 3] = data_list[2 ** N - 1]
##            data_list[2 ** N - 1] = tmp
##
##    print "YES"
##    for i in range(B_idx):
##        print data_list[i],
##    for i in range(2 ** N - 1, B_idx - 1, -1):
##        print data_list[i],
##
##    print

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, a, b = map(int, input().split())
def pop_count(x):
	res = 0
	for i in range(17):
		res += ((x>>i)%2 == 1)
	return res
if (pop_count(a^b)) % 2 == 0:
	print("NO")
else:
	print("YES")
	def f(m, x, y):
		if m == 1:
			if x == 0:
				return [0, 1]
			else:
				return [1, 0]

		res = [x]
		for i in range(m):
			if (x>>i) % 2  != (y>>i) % 2:
				diff = i
				break
		s = (x % (2**diff)) + (((x // (2**(diff+1))) * 2**(diff+1)) >> 1)
		t = (y % (2**diff)) + (((y // (2**(diff+1))) * 2**(diff+1)) >> 1)
		#return s, t
		u = s^1
		left = f(m-1, s, u)
		right = f(m-1, u, t)
		#print(left, right)
		x_bit, y_bit = (x>>diff) % 2, (y>>diff) % 2
		left = [l % (2**diff) + (2**diff * x_bit) + (((l // (2**diff)) * 2**diff) << 1) for l in left]
		right = [r % (2**diff) + (2**diff * y_bit) + (((r // (2**diff)) * 2**diff) << 1) for r in right]
		return left + right
	print(*f(n, a, b))

Submission status: Accepted

Solution code:
import sys
DBG = not True
DBG2 = not True
n,a,b =      map(int, input().split())
MAXM =  18
r = [0] * MAXM
s = [0] * MAXM
r[0] = [0]
r[1] = [0,1]
s[1] = [0,1]
p1a = [0,1,3,2]
p2a = [3,1,0,2,2,0,1,3]

def swiz(n,z,d):
    xpos = n - len(d)
    ypos = 0
    t = 0
    for i in range(n):
        if DBG2:
            print("sw lp i {} xp {} yp {} t {}".\
               format(i,xpos,ypos,t))
        if i in d:
            t += ((z >> xpos) & 1) << i
            xpos += 1
        else:
            t += ((z >> ypos) & 1) << i
            ypos += 1
    if  DBG2:
        print("sw z {} d {} ret {}".format(z,d,t))
    return t

for m in range(3,MAXM,2):
    s[m] = [0] * (2**m)
    for i in range(2**(m-2)):
        hi = s[m-2][i] << 2
        for j in range(4):
          s[m][4*i+j] = hi + \
            (p1a[j] if i == 0 else p2a[4*(i%2)+j])
          if DBG2:
              print("set s m {} i {} j {} - {}".\
                 format(m,i,j,s[m][4*i+j]))

for m in range(2,MAXM):
    r[m] = [0] * (2**m)
    for i in range(2**(m-1)):
        r[m][i  ] = r[m-1][i]
        r[m][2**m-1-i] = 2**(m-1) + r[m-1][i]

if DBG:
    for m in range(1,6):
        print(s[m])
    print("")
    for m in range(1,6):
        print(r[m])

z = a ^ b
cnt = 0
d = []
for i in range(MAXM):
    if z & (1<<i) != 0:
        cnt += 1
        d.append(i)
if cnt%2 == 0:
    print('NO')
    sys.exit(0)
else:
    print('YES')

sz = len(d)
if DBG:
    print("n {} a {} b {} sz {} d:".format(n,a,b,sz))
    print(d)

for i in range(2**sz):
    for j in range(2**(n-sz)):
        hi = (s[sz][i] << (n-sz))
        lo =  r[n-sz][j] if i%2 == 0 \
                         else r[n-sz][2**(n-sz)-1-j]
        z =  hi + lo
        sw = swiz(n,z,d)
        if DBG:
          print("i {} j {} hi {} lo {} z {} sw {}".\
               format(i,j,hi,lo,z,sw))
        sys.stdout.write(str(a^sw) + ' ')
print('')

Submission status: Accepted

Solution code:
import sys

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

BIT=0
for i in range(N):
    if (1<<i) & A!=(1<<i) & B:
        BIT+=1

if BIT%2==1:
    print("YES")
else:
    print("NO")
    sys.exit()

check=[0]*(1<<N)

ANS=[]
check[A]=1
check[B]=1

def route(x,i,j):#xから始まるルート,bit iは固定.j 残りbitの個数
    NOW=x
    ANS.append(NOW)
    check[NOW]=1

    for k in range(1<<j):
        for l in range(N):
            if check[NOW ^ (1<<l)]==0 and l!=i:
                NOW=NOW ^ (1<<l)
                check[NOW]=1
                ANS.append(NOW)
                break

    return NOW^(1<<i)

checkbit=[0]*N     
for i in range(N-1,-1,-1):
    for j in range(N):
        if (1<<j)&A!=(1<<j)&B and checkbit[j]==0:
            break
    A=route(A,j,i)
    checkbit[j]=1

ANS.append(B)
print(*ANS)

Submission status: Accepted

Solution code:
import sys

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

BIT=0
for i in range(N):
    if (1<<i) & A!=(1<<i) & B:
        BIT+=1

if BIT%2==1:
    print("YES")
else:
    print("NO")
    sys.exit()

check=[0]*(1<<N)

ANS=[]
check[A]=1
check[B]=1

def route(x,i,j):#xから始まるルート,bit iは固定.j 残りbitの個数
    NOW=x
    ANS.append(NOW)
    check[NOW]=1

    for k in range(1<<j):
        for l in range(N):
            if check[NOW ^ (1<<l)]==0 and l!=i:
                NOW=NOW ^ (1<<l)
                check[NOW]=1
                ANS.append(NOW)
                break

    return NOW^(1<<i)

checkbit=[0]*N     
for i in range(N-1,-1,-1):
    for j in range(N):
        if (1<<j)&A!=(1<<j)&B and checkbit[j]==0:
            break
    A=route(A,j,i)
    checkbit[j]=1

ANS.append(B)
print(*ANS)

Submission status: Accepted

Solution code:
import sys

def revBit(Ai):
    return '1' if Ai == '0' else '0'

def rec(binA, binB):
    if len(binA) == 1:
        return [binA, binB]

    for i, (Ai, Bi) in enumerate(zip(binA, binB)):
        if Ai != Bi:
            x = i
            Ax, Bx = Ai, Bi
            break

    binA2 = binA[:x] + binA[x+1:]
    binB2 = binB[:x] + binB[x+1:]
    binC = binA2[:-1] + revBit(binA2[-1])

    ptn1s = rec(binA2, binC)
    ptn2s = rec(binC, binB2)

    ptns = []
    for ptn1 in ptn1s:
        ptns.append(ptn1[:x] + Ax + ptn1[x:])
    for ptn2 in ptn2s:
        ptns.append(ptn2[:x] + Bx + ptn2[x:])

    return ptns


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

binA, binB = bin(A)[2:].zfill(N), bin(B)[2:].zfill(N)
numDiff = sum([Ai != Bi for Ai, Bi in zip(binA, binB)])

if numDiff % 2 == 0:
    print('NO')
    sys.exit()

ptns = rec(binA, binB)
print('YES')
print(' '.join([str(int(ptn, 2)) for ptn in ptns]))

Submission status: Accepted

Solution code:
import sys

ptn00 = [['00', '01', '11', '10'], ['10', '11', '01', '00']]
ptn11 = [['00', '01', '11', '10'], ['10', '00', '01', '11']]
ptnEven = ['01', '10']

# [00…0]（全ての桁が0）から[1…10…0]（先頭のnumDiff桁が1）まで、
# ちょうど1ビットずつ変化するパターン（重複なし）を生成する
def dfs(digit, ptnNow, parity, isLast):
    if digit == maxDigit:
        if N % 2:
            ptns.append(ptnNow)
        else:
            # Nが偶数の場合、長さを調整する
            ptns.append(ptnNow+ptnEven[parity][0])
            ptns.append(ptnNow+ptnEven[parity][1])
        return

    if digit <= numDiff//2 and parity and isLast:
        # [11]になるビットの場合、最後だけ基本パターンから逸脱する
        for v, p in enumerate(ptn11[1]):
            dfs(digit+1, ptnNow+p, v%2, isLast if v == 3 else 0)
    else:
        # [00]になる2ビットの場合
        for v, p in enumerate(ptn00[parity]):
            dfs(digit+1, ptnNow+p, v%2, isLast if v == 3 else 0)


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

binA, binB = bin(A)[2:].zfill(N), bin(B)[2:].zfill(N)
numDiff = sum([Ai != Bi for Ai, Bi in zip(binA, binB)])

if numDiff % 2 == 0:
    print('NO')
    sys.exit()

numSame = N - numDiff
maxDigit = 1 + numDiff//2 + numSame//2

ptns = []
dfs(1, '0', 0, False)
dfs(1, '1', 1, True)

# A→Bでの変化有無に応じて、各ビットを並べ替える
conv2digitPtns = []
digitDiff, digitSame = 0, numDiff
for i, (Ai, Bi) in enumerate(zip(binA, binB)):
    if Ai == Bi:
        conv2digitPtns.append(digitSame)
        digitSame += 1
    else:
        conv2digitPtns.append(digitDiff)
        digitDiff += 1

anss = []
for ptn in ptns:
    ans = ''
    for c in conv2digitPtns:
        ans += ptn[c]
    ans = int(ans, 2) ^ A
    anss.append(ans)

print('YES')
print(' '.join(map(str, anss)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Double(vec):
	m=len(vec)
	res=[]
	for i in range(0,m,2):
		res.extend([vec[i],vec[i]^m,vec[i+1]^m,vec[i+1]])
	return res

def Greedy(n):
	m=1<<n
	res=[0]*m
	vis=[False]*m
	vis[0]=True
	for i in range(1,m):
		x=res[i-1]
		for j in range(n):
			if not vis[x^(1<<j)]:
				x^=1<<j
				break
		vis[x]=True
		res[i]=x
	return res

def Perfect(n):
	if n==1:
		return [0,1]
	m=1<<n
	A=Greedy(n-1)
	B=Double(Perfect(n-2))
	B.reverse()
	for i in range(m>>1):
		B[i]^=m-1
	A.extend(B)
	return A

n,a,b=map(int,input().split())
m=1<<n
c=bin(a^b).count('1')
if not c&1:
	print('NO')
	exit()
tmp=Perfect(c)
for i in range(c,n):
	tmp=Double(tmp)
p=0
q=c
ans=[0]*m
for i in range(n):
	if (a^b)>>i&1:
		for j in range(m):
			ans[j]^=(((tmp[j]>>p)^(a>>i))&1)<<i
		p+=1
	else:
		for j in range(m):
			ans[j]^=(((tmp[j]>>q)^(a>>i))&1)<<i
		q+=1
print('YES\n',' '.join(str(i) for i in ans),sep='')

Submission status: Accepted

Solution code:
n,a,b = [int(i) for i in input().split()]

#n is the point in which to check wheter the mark is different
def f(n,a,b):
    if n==1:
        return [a,b]

    mask = 1<<(n-1)

    #if biggest bit of a == that of b
    if a & mask == b & mask:
        v1 = f(n-1, a, b)
        v2 = f(n-1, a^mask, v1[1]^mask)
        ret = [a]
        ret.extend(v2)
        ret.extend(v1[1:])
        return ret        
    else:
        # biggest bit of a and b is different
        v1 = f(n-1, a, a^1)
        v2 = f(n-1, a^1^mask, b)
        v1.extend(v2)
        return v1



#exclusive or
if bin(a^b).count("1") %2==0:
    print("NO")
else:
    print("YES")
    res = f(n,a,b)
    for p in res:
        print(p, end=" ")

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, a, b = [int(i) for i in input().split()]

if bin(a ^ b).count('1') % 2 == 0:
    print('NO')
    exit()

def dfs(i, a, b):
    if i == 1:
        return [a, b]
    d = (a ^ b) & -(a ^ b)
    ad = ((a & (~d ^ d - 1)) >> 1) + (a & d - 1)
    bd = ((b & (~d ^ d - 1)) >> 1) + (b & d - 1)
    c = ad ^ 1

    res1 = dfs(i - 1, ad, c)
    res2 = dfs(i - 1, c, bd)
    ans1 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & a) for r in res1]
    ans2 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & b) for r in res2]
    return ans1 + ans2

print('YES')
print(*dfs(n, a, b))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, a, b = [int(i) for i in input().split()]

if bin(a ^ b).count('1') % 2 == 0:
    print('NO')
    exit()

def dfs(i, a, b):
    if i == 1:
        return [a, b]
    d = (a ^ b) & -(a ^ b)
    ad = ((a & (~d ^ d - 1)) >> 1) + (a & d - 1)
    bd = ((b & (~d ^ d - 1)) >> 1) + (b & d - 1)
    c = ad ^ 1

    res1 = dfs(i - 1, ad, c)
    res2 = dfs(i - 1, bd, c)
    ans1 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & a) for r in res1]
    ans2 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & b) for r in res2[::-1]]
    return ans1 + ans2

print('YES')
print(*dfs(n, a, b))