Problem p03097 (python)

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

Buggy submission (verdict: Runtime Error):
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)