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: Runtime Error

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):
    return num ^ (1<<i) ^ (1<<j)

# 2つの数のbitが異なる桁を特定する
def different_digit(n: int, a: int, b: int):
    ret = -1
    for digit in range(n, -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)
    
    if dd == n-1:
        na = a & ~(1<<(n-1))
        nb = b & ~(1<<(n-1))
    else:
        na = swap_digit(a, n-1, dd) & ~(1<<(n-1))
        nb = swap_digit(b, n-1, dd) & ~(1<<(n-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: Runtime Error

Solution code:
def main():
    N, A, B = map(int, input().split())
 
    C = B - A
 
    #差のビット数を数える
    p = bin(C).count("1")
 
    if (N < p):
        print("NO")
        return
 
    if (0 == (N - p) % 2):
        print("NO")
        return
    
    print("YES")
    res = []
    a = A
    r = 1
    for i in range(N//2):
        if (0 == (C & r)):
            res.append(a)
            a ^= r
        r *= 2
    r = 1
    for i in range(N//2):
        if (0 == (C & r)):
            res.append(a)
            a ^= r
        r *= 2
    r = 1
    for i in range(N):
        if (0 < (C & r)):
            res.append(res[-1] | r)
        r *= 2
    res.append(B)
    print(" ".join([str(i) for i in res]))
    
main()

Submission status: Runtime Error

Solution code:
def main():
    N, A, B = map(int, input().split())
 
    C = B ^ A
 
    #差のビット数を数える
    p = bin(C).count("1")
 
    if (N < p):
        print("NO")
        return
 
    if (0 == (N - p) % 2):
        print("NO")
        return
    
    print("YES")
    res = []
    a = A
    r = 1
    for i in range(N//2):
        if (0 == (C & r)):
            res.append(a)
            a ^= r
        r *= 2
    r = 1
    for i in range(N//2):
        if (0 == (C & r)):
            res.append(a)
            a ^= r
        r *= 2
    r = 1
    for i in range(N):
        if (0 < (C & r)):
            res.append(res[-1] | r)
        r *= 2
    res.append(B)
    print(" ".join([str(i) for i in res]))
    
main()

Submission status: Runtime Error

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)

    for i in range(N-1):
        if (AA >> i) & 1 == (BB >i) &1:
            C = (AA & (-1 - (1<<i))) + (~AA & (1 << i))
            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: Runtime Error

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)

    for i in range(N-1):
        if (AA >> i) & 1 == (BB >i) &1:
            C = (AA & (-1 - (1<<i))) + (~AA & (1 << i))
            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)
    import pdb; pdb.set_trace()

    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: Runtime Error

Solution code:
import sys

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

def insert_bit(num1, num2, i):
    new_num = (num1 << 1) & ~(-1 + (1 << i + 1))
    new_num += num1 & (-1 + (1 << i + 1))
    new_num += num2 & (1 << i)
    return new_num

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

    for i in range(N):
        if A >> i & 1 != B >> i & 1:
            r_bit = i
            break

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

    for i in range(N - 1):
        if (AA & 1 << i) == (BB & 1 << i):
            CC = AA & (-1 - (1 << i)) + (~AA & (1 << i))
            break
    A_list = solve(N - 1, AA, CC)
    B_list = solve(N - 1, CC, 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: Runtime Error

Solution code:
import sys
DBG = not True
DBG2 = not True
n,a,b =      map(int, input().split())
MAXM =  19
r = [0] * MAXM
s = [0] * MAXM
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: Runtime Error

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[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: Runtime Error

Solution code:
import sys
DBG = not True
DBG2 = not True
n,a,b =      map(int, input().split())
MAXM = 6 # 18
r = [0] * MAXM
s = [0] * MAXM
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: Runtime Error

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: Runtime Error

Solution code:
N, A, B = [int(x) for x in input().split(' ') ]

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

if parityA % 2 == parityB % 2:
  print('NO')
else:
  print('YES')
  visited = [False] * (1 << N)
  visited[A] = True
  visited[B] = True
  def perm(n, a, b):
    if n == 1:
      return [a, b]
    for i in range(N):
      k = a ^ (1 << i)
      for j in range(N):
        l = b ^ (1 << j)
        for m in range(N):
          if not visited[k] and not visited[l] and k == l ^ (1<<m):
            visited[k] = True
            visited[l] = True
            left = perm(n - 1, a, k)
            right = perm(n - 1, l, b)
            return left + right
  list = perm(N, A, B)
  print(*list)

Submission status: Runtime Error

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):
        cnt += x & (2**i)
    if cnt % 2 == 1:
        print("NO")
    else:
        print("YES")
        print(*solve(N, A, B))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#define _CRT_SECURE_NO_WARNINGS
#define MOD 998244353
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <bitset>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstdio>
#include <utility>
#include <unordered_map>
#include <cmath>
#include <chrono>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> P;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)

inline ll madd(ll a, ll b) {
	a %= MOD;b %= MOD;
	return (a + b) % MOD;
}

inline ll msub(ll a, ll b) {
	a %= MOD;b %= MOD;
	a += MOD;
	return (a - b) % MOD;
}

inline ll mmul(ll a, ll b) {
	a %= MOD;b %= MOD;
	return (a*b) % MOD;
}

long long mpow(ll a, ll r) {
	long long res = 1;
	while (r > 0) {
		if (r & 1) res = res * a % MOD;
		a = a * a % MOD;
		r >>= 1;
	}
	return res;
}

inline ll minv(ll a) {
	a %= MOD;
	ll b = MOD, u = 0, v = 1;
	while (a) {
		ll t = b / a;
		b -= t * a; swap(a, b);
		u -= t * v; swap(u, v);
	}
	if (u < 0) u += MOD;
	return u;
}

inline ll mdiv(ll a, ll b) {
	a %= MOD;
	a *= minv(b);
	return a%MOD;
}

class BIT {
public:
	int n;
	vector<ll> bit;
	ll sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i&-i;
		}
		return s;
	}
	void add(int i, int x) {
		while (i <= n) {
			bit[i] += x;
			i += i&-i;
		}
	}
	BIT(int argn, vector<int> v) {
		n = argn;
		bit.push_back(0);
		ll partsum = 0;
		REP(i, n) {
			partsum += v[i];
			int k = i + 1;
			ll tosub = 0;
			for (int j = 1; j < k; j *= 2) {
				if (k&j != 0) {
					tosub = sum(k - j);
					break;
				}
			}
			bit.push_back(partsum - tosub);
		}
	}
};
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int cnt(int x) {
	int ret = 0;
	while (x > 0) {
		ret += x % 2;
		x /= 2;
	}
	return ret;
}

int get(int x, vector<P> vp) {
	for (P p : vp) {
		bool f=false, s=false;
		if ((x&(1 << p.first)) != 0) {
			x -= 1 << p.first;
			f = true;
		}
		if ((x&(1 << p.second)) != 0) {
			x -= 1 << p.second;
			s = true;
		}
		if(f) x += 1 << p.second;
		if(s) x += 1 << p.first;
	}
	return x;
}

int main(void) {
	int n, m, a, b, c;
	bool full = false;
	int arr[4] = { 0,2,3,1 };
	cin >> n >> a >> b;
	c = b^a;
	m = cnt(c);
	if (m % 2 == 0) {
		cout << "NO";
		return 0;
	}
	else {
		cout << "YES\n";
	}
	m--;
	int ind[20];
	int rev[20]; 
	REP(i, 20) {
		ind[i] = 0;
		if (m > 0) {
			rev[i] = 3;
			m -= 2;
		}
		else {
			rev[i] = 0;
		}
	}

	vector<int> v;
	REP(i, 1 << (n/2*2)) {
		v.push_back(0);
		REP(j, n / 2) {
			v[i] += arr[ind[j]] * (1<<(j*2));
		}
		int j = 0;
		int k = i+1;
		while (k > 0 && k % 4 == 0) {
			j++;
			k /= 4;
		}
		if (rev[j] > 0) {
			ind[j] += 3;
			rev[j]--;
		}
		else ind[j]++;
		ind[j] %= 4;
	}

	vector<int> vv;
	REP(i, 1 << (n/2*2)) {
		vv.push_back(v[i]);
		if (i % 2 == 0 && n % 2 == 1) {
			vv.push_back(v[i] + (1 << (n - 1)));
			vv.push_back(v[i+1] + (1 << (n - 1)));
		}
	}

	int cc = c,ccc=vv[(1<<n)-1];
	vector<P> vp;
	int aa = -1, bb = -1;
	REP(i, n) {
		if (cc % 2 != ccc % 2) {
			if (aa == -1) aa = i;
			else bb = i;
			if (bb != -1) {
				vp.push_back(P(aa, bb));
				aa = -1;bb = -1;
			}
		}
		cc /= 2;
		ccc /= 2;
	}

	for (int i : vv) {
		int j = get(i, vp) ^ a;
		cout << j << " ";
	}
	return 0;
}

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;
ll pow(ll x,ll n){
    ll ans = 1;
    while(n > 0){
        if(n%2 == 1) ans = ans * x;
        x = x * x;
        n = n >> 1;
    }
    return ans;
}
int n,a,b;
int used[300000] = {0};
vector<int> G[300000];

void dfs(int s){
    cout << s << " ";
    used[s] = 1;
    int mx = -1;
    int next;
    //cerr << s << endl;
    for(auto x:G[s]){
        int cnt = 0;
        if(used[x] == 1)continue;
        for(auto y:G[x]){
            if(used[y] == 0)cnt++;
        }
        if(cnt > mx){
            mx = cnt;
            next = x;
            //cerr << cnt << " "; 
        }
    }
    if(mx != -1)dfs(next);
    return;
}


signed main(){
    
    cin >> n >> a >> b;
    int P = pow(2,n);
    int x = a;
    int y = b;
    int cnt = 0;
    rep(i,20){
        if(x%2 == y%2)cnt++;
        x /= 2;
        y /= 2;
    }
    if(cnt%2 == 0){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;

    for(int i = 0;i < P;i++){
        for(int j = 0;j < n;j++){
            int t = i^(1LL<<j);
            G[t].push_back(i);
        }
    }
    // for(int i = 0;i < P;i++){
    //     cerr << i << endl;
    //     for(auto z:G[i])cerr << z << " ";
    //     cerr << endl;
    // }
    used[b] = 1;
    dfs(a);
    cout << b << endl;

    
    
    
    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://agc031.contest.atcoder.jp/tasks/agc031_a
// rm -r -f test;oj dl http://abc107.contest.atcoder.jp/tasks/abc107_b

Submission status: Runtime Error

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

twoN = 2**N
visited = 1 << A
cache = {}
def dfs(node, visited, path, depth):
    neighbor_list = [node ^ (1<<mask) for mask in range(N)]
    if depth == twoN-2 and B in neighbor_list:
        print("YES\n" + " ".join([str(i) for i in path + [B]]))
        return True
    elif B in neighbor_list:
        neighbor_list.remove(B)
    for neighbor in neighbor_list:
        if not visited & (1 << neighbor):
            if not cache.get((neighbor, visited), True): continue
            if dfs(neighbor, visited ^ (1 << neighbor), path +
                    [neighbor], depth+1):
                return True
            cache[(neighbor, visited)] = False                                                                 
    return False
    
if not dfs(A, visited, [A], 0):
    print("NO")

Submission status: Runtime Error

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

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

if (a ^ b) % 2 == 1 and (a ^ b) != 1:
    print('NO')
    exit()

def dfs(i, a):
    if i == 1:
        return [a & 1, ~a & 1]
    res = dfs(i - 1)
    if a & ((1 << i) - 1) != res[0]:
        res.reverse()
    return [(a & (1 << (i - 1))) + r for r in res] + [((~a) & (1 << (i - 1))) + r for r in res[::-1]]

ans = [(1 << (n - 1)) + r for r in dfs(n - 1, b)[::-1]] + [r for r in dfs(n - 1, a)]
index = ans.index(a)
print('YES')
print(*(ans[index:] + ans[:index]))

Submission status: Runtime Error

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

if (a ^ b) % 2 == 1 and (a ^ b) != 1:
    print('NO')
    exit()

def dfs(i, a):
    if i == 1:
        return [a & 1, ~a & 1]
    res = dfs(i - 1)
    if a & ((1 << i) - 1) != res[0]:
        res.reverse()
    return [(a & (1 << (i - 1))) + r for r in res] + [((~a) & (1 << (i - 1))) + r for r in res[::-1]]

ans = [(1 << (n - 1)) + r for r in dfs(n - 1, b)[::-1]] + [r for r in dfs(n - 1, a)]
index = ans.index(a)
print('YES')
print(*(ans[index:] + ans[:index]))

Submission status: Runtime Error

Solution code:
# test for NO is correct 
N,A,B= list(map(int,input().split()))
B1 = A^B


from collections import defaultdict
d = defaultdict(list)
for i in range(2**N):
    bits_total = bin(i)[2:].count('1')
    d[bits_total].append(i)
def count_bits(n):
    return bin(n)[2:].count('1')

def int_to_bin(n):
    return list(reversed(list((map(lambda x:x=='1',bin(n)[2:])))))+[0]*N
def bin_to_int(V):
    ans = 0
    for i,val in enumerate(V):
        ans += val *(2 **i)
    return ans

assert bin_to_int([1])==1
assert bin_to_int([0,1])==2

def movable(i):
    res = set()
    for bit_num in range(N):
        if i>= 2**bit_num and bin(i)[2:][-bit_num-1]=='1':
            res.add(i - 2**bit_num)
        else:
            res.add(i+2**bit_num)
    return res

used = set()
i=0
next = -1
used.add(0)
order = [0]
try:
    while len(used) < 2**N:
        next = max(movable(i) - used)
        used.add(next)
        i=next
        order.append(i)
except:
    print("NO")
    exit()

if count_bits(next)!= count_bits(B1):
    print("NO")
    exit()
raise


def find_all(x):
    res = []
    for bit_num in range(N):
        if x>= 2**bit_num and bin(x)[2:][-bit_num-1]=='1':
            res.append(bit_num)
    return res
a= find_all(B1)
b= find_all(next)

def convert(x,p,q):
    V = int_to_bin(x)
    for i in range(len(p)):
        tmp = V[p[i]]
        V[p[i]]=V[q[i]]
        V[q[i]]= tmp
    return bin_to_int(V)

print("YES")
print(" ".join([str(convert(n,a,b) ^A) for n in order]))

Submission status: Runtime Error

Solution code:
N, A, B = map(int, input().split())                                                                            
cache = {}
twoN = 2**N
visited = 1 << A
def dfs(node, visited, path, depth):
    mask = 1 
    while mask < twoN:
        neighbor = node ^ mask
        if neighbor == B:
            if depth == twoN-2:
                print("YES")
                print(" ".join([str(i) for i in path + [B]]))
                return True
            else:
                mask <<= 1
                continue
        if not cache.get((neighbor, depth), True):
            mask <<= 1
            continue 
        if not visited & (1 << neighbor):
            if dfs(neighbor, visited ^ (1 << neighbor), path + [neighbor],
                    depth+1):
                return True
            cache[(neighbor, depth)] = False
        mask <<= 1
    return False
  
if not dfs(A, visited, [A], 0):
    print("NO")

Submission status: Runtime Error

Solution code:
N, A, B = map(int, input().split())                                                                            
cache = {}
twoN = 2**N
visited = 1 << A
def dfs(node, visited, path, depth):
    mask = 1 
    while mask < twoN:
        neighbor = node ^ mask
        if neighbor == B:
            if depth == twoN-2:
                print("YES")
                print(" ".join([str(i) for i in path + [B]]))
                return True
            else:
                mask <<= 1
                continue
        if not cache.get((neighbor, depth), True):
            mask <<= 1
            continue 
        if not visited & (1 << neighbor):
            if dfs(neighbor, visited ^ (1 << neighbor), path + [neighbor],
                    depth+1):
                return True
            cache[(neighbor, depth)] = False
        mask <<= 1
    return False
  
  if not dfs(A, visited, [A], 0):
    print("NO")

Submission status: Runtime Error

Solution code:
import sys
import time
import random
sys.setrecursionlimit(100000000)
N, A, B = map(int, input().split())
sTime = time.time()

P = [-1] * N
Q = [0] * (2**N)
X = [0] * (2**N)
X[0] = 1
X[1] = 1
Y = [1<<i for i in range(N)]
Z = [0]

def calc(k, l, M):
    aa = 0
    bb = 0
    done = [0] * N
    for i in range(M):
        # print("M, i, k,aa,Y=", M, i, k, aa, Y)
        while k & Y[aa] == 0:
            aa += 1
        while l & Y[bb] == 0:
            bb += 1
        P[aa] = bb
        done[bb] = 1
        aa += 1
        bb += 1
    j = 0
    # print(P)
    # print(done)
    for i in range(N):
        if P[i] >= 0:
            continue
        while done[j] == 1:
            j += 1
        P[i] = j
        j += 1

def change(n):
    ret = 0
    for i in range(N):
        if n & (1<<i):
            ret += 1<<P[i]
    return ret

def dc(n):
    return sum(map(int, list(bin(n)[2:])))


def dfs(n, c):
    if time.time() - sTime > 1.75:
        return -1
    for i in range(N):
        m = n ^ Y[i]
        # print(n, i, m, c)
        if c == 2**N - 2 and m == 1:
            X[m] = 1
            Z.append(m)
            return 1
        if X[m] == 0 and m != 1:
            X[m] = 1
            Z.append(m)
            # print(Z)
            r = dfs(m, c+1)
            if r:
                return r
            if r < 0:
                return -1
            X[m] = 0
            Z.pop()
    return 0

if (dc(A) + dc(B)) % 2 == 0:
    print("NO")
else:
    r = dfs(0, 0)
    for i in range(2**N):
        if Z[i] == A:
            Z = Z[i:] + Z[:i]
            break
    # print(X, Y, Z)
    if r < 0:
        print("NO")
    else:
        # print("A", Z[:10], Z[-10:])
        mi = 99999
        while mi > 0:
            # for i in range(3, 2**N-1, 2):
            i = random.randrange(max(2**N-1001, 1),2**N-1,2)
            if Z[i-1]^Z[-1] in Y:
                Z = Z[:i] + Z[i:][::-1]
                mi = abs(dc(Z[-1]) - dc(B))
        # print("A", Z[:10], Z[-10:])
        # print("(Z[-1], B, dc(B))", Z[-1], B, dc(B))
        calc(Z[-1], B, dc(B))
        # print("P=", P)
        for i in range(N):
            s = 1<<P[i]
            t = 1<<i
            for j in range(2**N):
                if j & t:
                    Q[j] += s
        Z = [Q[z] for z in Z]
        # print(Z[:10], Z[-10:])
        print("YES")
        print(*Z)

Submission status: Runtime Error

Solution code:
[N, A, B] = list(map(int, input().split()))
gray_A = decode_gray(A)
gray_B = decode_gray(B)
if abs(gray_A - gray_B) == 1:
    print("Yes")
    if gray_A > gray_B:
        for n in range(gray_A, 2 ** N - 1):
            print(encode_gray(n), end=" ")
        for n in range(0, gray_B):
            print(encode_gray(n), end=" ")
        print(B)
    else:
        for n in range(gray_A, -1, -1):
            print(encode_gray(n), end=" ")
        for n in range(2 ** N - 1, gray_B, -1):
            print(encode_gray(n), end=" ")
        print(B)
else:
    print("No")