Problem p03097 (python)

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

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

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

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

Buggy submission (verdict: Runtime Error):
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(N):
        if Z[i] == A:
            Z = Z[i:] + Z[:i]
    # 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)

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

Buggy submission (verdict: Runtime Error):
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)
    # print(X, Y, Z)
    if r < 0:
        print(1/0)
    else:
        # print("A", Z[:10], Z[-10:])
        mi = 99999
        while mi > 0:
            # for i in range(3, 2**N-1, 2):
            i = random.randrange(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)