Problem p02609 (python)

Fixed submission:
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)

Buggy submission (verdict: Runtime Error):
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
dp[0] = 0
dp[1] = 1
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
for i in range(1, 18):
    pcs[2**i] = 1
    pcs[2**i-1] = i
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

dp = [-1] * ((2*10**5)+1)
pcs = [-1] * ((2*10**5)+1)
pcs[0] = 0
pcs[1] = 1
pcs[2] = 1
dp[0] = 0
def f(n):
    if dp[n] >= 0:
        return dp[n]
    if pcs[n] >= 0:
        pc = pcs[n]
    else:
        pc = bin(n).count('1')
        pcs[n] = pc
    nn = n%pc
    d = f(nn)+1
    dp[n] = d
    return d

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp //= 2
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)
dp = [-1] * ((2*10**5)+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)
    if (nx>>i)&1:
        r = (nx-tmp)%(pc-1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
    else:
        r = (nx+tmp)%(pc+1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)
dp = [-1] * (2*10**5+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1

    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)
    if (nx>>i)&1:
        nx -= tmp
        r = nx%(pc-1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx += tmp
    else:
        nx += tmp
        r = nx%(pc+1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx -= tmp

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**6+1)
def f(n):
    if n < 10**6 and dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1

    d = f(nn) + 1
    if n < 10**6:
        dp[n] = d
    return d

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
nx = int(X, 2)
def f(n):
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    return f(nn) + 1

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**7+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp

Buggy submission (verdict: Runtime Error):
n = int(input())
X = input()
nx = int(X, 2)
dp = [-1] * (10**7+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1
    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)

    if (nx>>i)&1:
        nx -= tmp
        print(f(nx))
        nx += tmp
    else:
        nx += tmp
        print(f(nx))
        nx -= tmp