Problem p02609 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**8)

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[-i-1] = base%(bit_cnt+1)
    if x[-i-1] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)

base = 1
if bit_cnt == 1:
    # mod取れない
    pass
else:
    for i in range(n):
        neg[-i-1] = base%(bit_cnt-1)
        if x[-i-1] == '1':
            # 同時にmod(bit_cnt-1)の法でトータルを作成
            neg_total = (neg_total + base) % (bit_cnt-1)
        base = (base*2) % (bit_cnt-1)

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[i] = base%(bit_cnt+1)
    if x[n-i-1] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = (pos_total + base) % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)
pos = pos[::-1]

base = 1
for i in range(n):
    neg[i] = base%(bit_cnt-1)
    if x[n-i-1] == '1':
        # 同時にmod(bit_cnt-1)の法でトータルを作成
        neg_total = (neg_total + base) % (bit_cnt-1)
    base = (base*2) % (bit_cnt-1)
neg = neg[::-1]

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

n = int(input())
x = list(input())
bit_cnt = x.count('1')

# bitを一つ増やす場合
pos = [0] * n
pos_total = 0

# bitを一つ減らす場合
neg = [0] * n
neg_total = 0

base = 1
for i in range(n):
    pos[i] = base%(bit_cnt+1)
    if x[n-i-1] == '1':
        # 同時にmod(bit_cnt+1)の法でトータルを作成
        pos_total = pos_total + base % (bit_cnt+1)
    base = (base*2) % (bit_cnt+1)
pos = pos[::-1]

base = 1
for i in range(n):
    neg[i] = base%(bit_cnt-1)
    if x[n-i-1] == '1':
        # 同時にmod(bit_cnt-1)の法でトータルを作成
        neg_total = neg_total + base % (bit_cnt-1)
    base = (base*2) % (bit_cnt-1)
neg = neg[::-1]

def popcount(n):
    s = list(bin(n)[2:])
    return s.count('1')

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        # memo[n] = ret
        return ret

ans = []
for i in range(n):
    if x[i] == '0':
        st = (pos_total + pos[i]) % (bit_cnt+1)
        print(dfs(st, depth=1))
    elif bit_cnt == 1:
        # コーナーケース：すべてのbitが0となる
        print(0)
    else:
        st = (neg_total - neg[i]) % (bit_cnt-1)
        print(dfs(st, depth=1))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

n = int(input())
xs = list(input())[::-1]

x = 0
for i in range(n):
    if xs[i] == '1':
        x+=2**i

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

memo = {}
memo[0] = 1
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n] - 1
    else:
        ret = dfs(n%popcount(n), depth+1)
        memo[n] = ret
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

n = int(input())
xs = list(input())[::-1]

x = 0
for i in range(n):
    if xs[i] == '1':
        x+=2**i

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

memo = {}
memo[0] = 0
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

n = int(input())
xs = list(input())[::-1]

x = 0
for i in range(n):
    if xs[i] == '1':
        x+=2**i

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

memo = {}
memo[0] = 0
memo[1] = 1
memo[2] = 2
def dfs(n, depth=0):
    if n in memo:
        return depth + memo[n]
    else:
        ret = dfs(n%popcount(n), depth+1)
        return ret

ans = []
for i in range(n):
    ans.append(dfs(x^(1<<i)))
for a in ans[::-1]:
    print(a)