Problem p02609 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()

A = [0]
for i in range(1,2*10**5):
    a = 0
    r = i
    for j in range(18):
        a += (i>>j)&1
    r %= a
    if r == 0:
        A.append(1)
    else:
        A.append(1+A[r])

X = LS2()

b = 0
for i in range(N):
    if X[i] == '1':
        b += 1
if b >= 2:
    c = b-1
    d = b+1

    r1 = 0
    r2 = 0

    amari1 = [1]
    amari2 = [1]
    for i in range(1,N):
        amari1.append((amari1[-1]*2) % c)
        amari2.append((amari2[-1]*2) % d)
    amari1.reverse()
    amari2.reverse()
    for i in range(N):
        if X[i] == '1':
            r1 += amari1[i]
            r1 %= c
            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':
            e = r1
            e -= amari1[i]
            e %= c
            ANS.append(A[e]+1)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f]+1)
else:
    d = b + 1
    r2 = 0


    amari2 = [1]
    for i in range(1, N):
        amari2.append((amari2[-1] * 2) % d)
    amari2.reverse()

    for i in range(N):
        if X[i] == '1':

            r2 += amari2[i]
            r2 %= d
    ANS = []
    for i in range(N):
        if X[i] == '1':

            ANS.append(0)
        else:
            f = r2
            f += amari2[i]
            f %= d
            ANS.append(A[f] + 1)


print(*ANS,sep='\n')

Buggy submission (verdict: Runtime Error):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

A = [0]*(2*10**5+1)  # Ai = f(i)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  # Xの各桁の和

if r >= 2:
    B = [1] + [0]*(N-1)  # Bi = 2**i mod (r-1)
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    b,c = 0,0  # b,c = X mod (r-1),X mod (r+1)
    for i in range(1,N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(1+A[(b-B[i]) % (r+1)])

else:
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    c = 0  # c = X mod (r+1)
    for i in range(1,N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 0:
    print(1)
    exit()

A = [0]*(2*10**5+1)  # Ai = f(i)
for i in range(1,2*10**5+1):
    k = 0
    for j in range(18):
        if (i >> j) & 1:
            k += 1
    A[i] = A[i % k] + 1


r = sum(X)  # Xの各桁の和

if r >= 2:
    B = [1] + [0]*(N-1)  # Bi = 2**i mod (r-1)
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    b,c = 0,0  # b,c = X mod (r-1),X mod (r+1)
    for i in range(N):
        B[i] = (B[i-1]*2) % (r-1)
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            b += B[i]
            b %= r-1
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(1+A[(b-B[i]) % (r+1)])

else:
    C = [1] + [0]*(N-1)  # Ci = 2**i mod (r+1)
    c = 0  # c = X mod (r+1)
    for i in range(N):
        C[i] = (C[i-1]*2) % (r+1)
        if X[i] == 1:
            c += C[i]
            c %= r+1

    for i in range(N-1,-1,-1):
        if X[i] == 0:
            print(1+A[(c+C[i]) % (r-1)])
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X = LI2()
X.reverse()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0]*(2*10**5)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り
xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')