Problem:


Score : 400 points

Problem Statement

Let \mathrm{popcount}(n) be the number of 1s in the binary representation of n.
For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and \mathrm{popcount}(0) = 0.

Let f(n) be the number of times the following operation will be done when we repeat it until n becomes 0: "replace n with the remainder when n is divided by \mathrm{popcount}(n)." (It can be proved that, under the constraints of this problem, n always becomes 0 after a finite number of operations.)

For example, when n=7, it becomes 0 after two operations, as follows:

\mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.

\mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.

You are given an integer X with N digits in binary.
For each integer i such that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top is inverted.
Find f(X_1), f(X_2), \ldots, f(X_N).

Constraints

1 \leq N \leq 2 \times 10^5

X is an integer with N digits in binary, possibly with leading zeros.

Input

Input is given from Standard Input in the following format:

N
X

Output

Print N lines. The i-th line should contain the value f(X_i).

Sample Input 1

3
011

Sample Output 1

2
1
1

X_1 = 7, which will change as follows: 7 \rightarrow 1 \rightarrow 0. Thus, f(7) = 2.

X_2 = 1, which will change as follows: 1 \rightarrow 0. Thus, f(1) = 1.

X_3 = 2, which will change as follows: 2 \rightarrow 0. Thus, f(2) = 1.

Sample Input 2

23
00110111001011011001110

Sample Output 2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3



Sample input:
3
011


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=0
chk0=chk1=chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk0+=pow(2,i)
        chk1+=pow(2,i,b+1)
        chk2+=pow(2,i,b-1)
#print(chk0,chk1,chk2)
#print(bin(chk0+1),bin(chk1),bin(chk2))
#print(bin(chk0+1).count("1"),bin(chk1).count("1"),bin(chk2).count("1"))
#print((chk1+1)%(b+1))
#print(chk0+1,bin(chk0+1).count("1"))
#print((chk0+1)%bin(chk0+1).count("1"))
#exit()
l=[]
#chk1=chk1+b+1
#chk2=chk2+b-1
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    ans=0
    f=1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=0
chk0=chk1=chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk0+=pow(2,i)
        chk1+=pow(2,i,b+1)
        chk2+=pow(2,i,b-1)
#print(chk0,chk1,chk2)
#print(bin(chk0+1),bin(chk1),bin(chk2))
#print(bin(chk0+1).count("1"),bin(chk1).count("1"),bin(chk2).count("1"))
print((chk1+1)%(b+1))
#print(chk0+1,bin(chk0+1).count("1"))
#print((chk0+1)%bin(chk0+1).count("1"))
#exit()
l=[]
#chk1=chk1+b+1
#chk2=chk2+b-1
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    ans=0
    f=1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")
X10_pl = X10%(one_num+1)
X10_mi = X10%(one_num-1)

for i in range(N):
    target = int(X[i])
    
    if target == 0:
        ones = one_num + 1
        plus = pow(2,N-i-1,ones)
        Xnow = (X10_pl + plus)%ones
        
    else:
        if one_num == 1:
            print(0)
            continue
        ones = one_num-1
        plus = -pow(2,N-i-1,ones)
        Xnow = (X10_mi + plus)%ones

    count=1
    
    while Xnow > 0:
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
        
    print(count)

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

# input
N = int(input())
X = input()


def popcount(n):
    return bin(n).count("1")


def solve(n):
    if n == 0:
        return 0
    c = popcount(n)
    return 1 + solve(n % c)


def main():
    c = X.count("1")
    a, b = 0, 0
    for i in range(N):
        if X[-1 - i] == "1":
            a = (a + pow(2, i, c - 1)) % (c - 1)
            b = (b + pow(2, i, c + 1)) % (c + 1)
    for i in range(N):
        if c == 1 and X[i] == "1":
            print(0)
            continue
        if X[i] == "1":
            m = c - 1
            w = (a - pow(2, N - 1 - i, m)) % m
        else:
            m = c + 1
            w = (b + pow(2, N - 1 - i, m)) % m
        ans = solve(w) + 1
        print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret

def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

N = int(input())
X = input()

source_one = X.count('1')

import collections

count = collections.defaultdict(int)
count[1] = 1
count[2] = 1

source_n = int(X, 2)

kijou = 2 ** N

for i in range(N):
    kijou //= 2
    if X[i] == '1':
        one_count = source_one - 1
        original_n = source_n - kijou
    else:
        one_count = source_one + 1
        original_n = source_n + kijou

    if one_count == 0:
        count[original_n] = 1
        print(1)

    n = original_n % one_count



    count[original_n] = f(n) + 1
    print(count[original_n])

Submission status: Runtime Error

Solution code:
def popcount(n):
    ret = 0
    while n:
        ret += n & 1
        n >>= 1
    return ret

def f(n):
    t = 0
    while n:
        t += 1
        n %= popcount(n)
    return t

N = int(input())
X = input()

source_one = X.count('1')

import collections

count = collections.defaultdict(int)
count[1] = 1
count[2] = 1

source_n = int(X, 2)

kijou = 2 ** N

for i in range(N):
    kijou //= 2
    if X[i] == '1':
        one_count = source_one - 1
        original_n = source_n - kijou
    else:
        one_count = source_one + 1
        original_n = source_n + kijou

    if original_n in count:
        print(count[n])
        continue
    if original_n % one_count == 0:
        count[n] = 1
        print(1)
        continue

    n = original_n % one_count

    count[original_n] = f(n) + 1
    print(count[original_n])

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
#!python3

# input
N = int(input())
X = input()


def popcount(n):
    return bin(n).count("1")


def solve(n):
    if n == 0:
        return 0
    c = popcount(n)
    return 1 + solve(n % c)


def main():
    c = X.count("1")
    a, b = 0, 0
    for i in range(N):
        if X[-1 - i] == "1":
            a = (a + pow(2, i, c - 1)) % (c - 1)
            b = (b + pow(2, i, c + 1)) % (c + 1)
    for i in range(N):
        if c == 1 and X[i] == "1":
            print(0)
            continue
        if X[i] == "1":
            m = c - 1
            w = (a - pow(2, N - 1 - i, m)) % m
        else:
            m = c + 1
            w = (b + pow(2, N - 1 - i, m)) % m
        ans = solve(w) + 1
        print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi) -1
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                dq.append((j, y, cnt))
            else:
                y = x | bi[j]
                if y > cnt0: continue
                cache[y] = cache[y % cnt] + 1
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi) -1
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                dq.append((j, y, cnt))
            else:
                y = x | bi[j]
                if y > cnt0: continue
                cache[y] = cache[y % cnt] + 1
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print("\n".join(map(str, [1]*N)))
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi)
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                if j < ls:
                    dq.append((j, y, cnt))
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        raise 1
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi)
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y > cnt0: break

                cache[y] = cache[y % cnt] + 1

                j += 1
                if j < ls:
                    dq.append((j, y, cnt))
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        raise 1
        print("\n".join(map(str, [1]*N)))
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    #f3 = f2()
    def f2():
        cache = [0] * (cnt0 + 1)
        i = 1
        bi = []
        while i <= cnt0:
            bi.append(i)
            i <<= 1
        from collections import deque
        dq = deque([(0, 0, 0)])
        ls = len(bi)
        while dq:
            i, x, cnt = dq.popleft()

            cnt += 1
            for j in range(i, ls):
                y = x | bi[j]

                if y >= cnt0: break

                cache[y] = cache[y % cnt] + 1
                dq.append((j+1, y, cnt))
        def f(x):
            return cache[x]
        #f.cache = cache
        return cache


    memo = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + memo[n]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
X10 = int(X,2)
one_num = X.count("1")



for i in range(N):
    target = int(X[i])
    if target == 0:
        ones = one_num + 1
        plus = pow(2,N-i-1,ones)
        
    else:
        ones = one_num-1
        plus = -pow(2,N-i-1,ones)
        
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")
xp = X10 % (one_num+1)
xm = X10 % (one_num-1)

for i in range(N):
    target = int(X[i])
    count=0
    if target == 0:
        plus = pow(2,N-i-1,xp)
    else:
        plus = -pow(2,N-i-1,xm)
    if X10+plus == 0:
        print(count)
        continue
    if target == 0:
        ones = one_num+1
        Xnow = (xp + plus)%ones
    else:
        ones = one_num-1
        Xnow = (xm + plus)%ones
    count += 1
    while Xnow > 0:
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
    print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")
xp = X10 % (one_num+1)
xm = X10 % (one_num-1)

for i in range(N):
    target = int(X[i])
    count=0
    if target == 0:
        plus = pow(2,N-i-1)
    else:
        plus = -pow(2,N-i-1)
    if X10+plus == 0:
        print(count)
        continue
    if target == 0:
        ones = one_num+1
        Xnow = (xp + plus)%ones
    else:
        ones = one_num-1
        Xnow = (xm + plus)%ones
    count += 1
    while Xnow > 0:
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
    print(count)

Submission status: Runtime Error

Solution code:
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    d1 = []
    d2 = []
    d11 = 1
    d22 = 1
    for i in range(1, N+1):
        d1.append(d11)
        d11 *= 2
        d11 %= t-1
        d2.append(d22)
        d22 *= 2
        d22 %= t+1
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ d1[N-i-1]
        elif t != 1:
            cur_bits = t + 1
            x = V ^ d2[N-i-1]
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = "{:0b}".format(x).count("1")
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    d1 = []
    d2 = []
    d11 = 1
    d22 = 1
    for i in range(1, N+1):
        d1.append(d11)
        d11 *= 2
        d11 %= t-1
        d2.append(d22)
        d22 *= 2
        d22 %= t+1
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ d1[N-i-1]
        elif t != 1:
            cur_bits = t + 1
            x = V ^ d2[N-i-1]
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = 0
            T = "{:0b}".format(x)
            for t in T:
                if t == "1":
                    cur_bits += 1
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def pcount(x):
    # cnt = 0
    # while x > 0:
    #     cnt += (x & 1)
    #     x = x >> 1
    # return cnt
    return bin(x).count('1')

cache = {}


def f(x):
    if x == 0:
        return 0
    if x in cache:
        return cache[x]
    cnt = f(x % pcount(x)) + 1
    cache[x] = cnt
    return cnt


def main():
    N = int(input())
    X = input()

    pcount = X.count('1')
    pcountP = pcount + 1
    pcountM = pcount - 1

    xint = int(X, 2)
    pcountP_mod = xint % pcountP
    pcountM_mod = xint % pcountM
    

    for i in range(N):
        x2 = X
        if x2[i] == "0":
            x2 = x2[0:i] + '1' + x2[i+1:]
            x = (pcountP_mod + (2 ** (N - i - 1)) % pcountP) % pcountP
            # x = int(x2, 2) % pcountP
        else:
            x2 = x2[0:i] + '0' + x2[i+1:]
            if pcountM == 0:
                print("0")
                continue
            x = (pcountM_mod  - (2 ** (N - i - 1) + pcountM) % pcountM) % pcountM
            # x = int(x2, 2) % pcountM
        print(f(x) + 1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_p - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_m + p[i-1]) % pc_p
        print(rest[a] + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as d

def c(n):
  if n == 0: return 0
  else: return 1 + c(n & (n - 1)) 

memo = d(int)
memo[0]=0
n = int(input())
x = input()

for i in range (n):
  f = x[:i]
  if int(x[i]):f+='0'
  else:f+='1'
  f+=x[i+1:]
  f = int(f, 2)
  if f in memo.keys():
    print(memo[f])
  else:
    ans = 0
    r = f%c(f)
    while r:
      r = r%c(r)
      ans+=1
      if r in memo.keys():ans+=memo[r];break
    memo[f]=ans
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        if pc_m != 0:
            a = (x - m[i-1]) % pc_m
            print(rest[a] + 1)
        else:
            print(0)
    else:
        a = (x + p[i-1]) % pc_p
        print(rest[a] + 1)

Submission status: Runtime Error

Solution code:
n=int(input())
x=input()
p=0
chk1=0
chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
         chk1+=pow(2,i,b+1)
         chk2+=pow(2,i,b-1)
l=[]
chk1=chk1+b+1
chk2=chk2+b-1
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    #print("#",t)
    ans=0
    while t:
        t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l:
    print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        if pc_m != 0:
            a = (x - m[i-1]) % pc_m
            print(rest[a] + 1)
        else:
            print(0)
    else:
        a = (x + p[i-1]) % pc_p
        print(rest[a] + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        if pcm == 0:
            return -1
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        n = rev(x, i)
        if n == -1:
            print(0)
        else:
            print(f(n, 1))

Submission status: Runtime Error

Solution code:
def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = xd = 0
elif p == 1:
    xi = X % 2
    xd = 0
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    k = 1 << (N - 1 - i)
    if X & k:
        x = (xd - k) % (p - 1)
    else:
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        n = rev(x, i)
        if n == 0:
            print(0)
        else:
            print(f(n, 1))

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
memo = {}
X_int = int(X, 2)


def popcount(n: int):
    x = bin(n)[2:]
    return x.count("1")


pcf = popcount(int(X, 2))
pcm = pcf - 1
pcp = pcf + 1
xm = X_int % pcm
xp = X_int % pcp


def f(n: int, ops: int):

    while n != 0:
        n %= popcount(n)
        ops += 1
    return ops


def rev(x: str, i: int):
    if x == "1":
        n = (xm - (pow(2, N-i-1, pcm))) % pcm
    else:
        n = (xp + (pow(2, N-i-1, pcp))) % pcp
    return n


if __name__ == "__main__":
    for i, x in enumerate(X):
        print(f(rev(x, i), 1))

Submission status: Runtime Error

Solution code:

def pcount(x):
    cnt = 0
    while x > 0:
        cnt += (x & 1)
        x = x >> 1
    return cnt

def f(x):
    cnt = 0
    while x > 0:
        x = x % pcount(x)
        cnt += 1
    return cnt


def main():
    N = int(input())
    X = input()

    pcount = X.count('1')
    pcountP = pcount + 1
    pcountM = pcount - 1

    for i in range(N):
        x2 = X
        if x2[i] == "0":
            x2 = x2[0:i] + '1' + x2[i+1:]
            x = int(x2, 2) % pcountP
        else:
            x2 = x2[0:i] + '0' + x2[i+1:]
            x = int(x2, 2) % pcountM
        print(f(x) + 1)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = []
    for v in [1, -1]:
        x = cnt0 + v
        y = X % x if x else 0
        dc.append((x, v, y, [1, N-1]))

    ans = [0] * N
    for i in reversed(range(N)):
        cnt, v, n, m1 = dc[0 if S[i] == "0" else 1]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()
original_pop_cnt = x.count("1")

pop_cnt_add = original_pop_cnt + 1
pop_cnt_sub = original_pop_cnt - 1

n_after_once_popcount_add = 0
n_after_once_popcount_sub = 0

for i in range(n):
    n_after_once_popcount_add = (n_after_once_popcount_add * 2 + int(x[i])) % pop_cnt_add
    n_after_once_popcount_sub = (n_after_once_popcount_sub * 2 + int(x[i])) % pop_cnt_sub

pow_add = [1] * (n + 100)
pow_sub = [1] * (n + 100)

for i in range(1, n + 100):
    pow_add[i] = (pow_add[i-1]*2) % pop_cnt_add
    pow_sub[i] = (pow_sub[i-1]*2) % pop_cnt_sub

def f(nex):
    ans = 0
    num = nex
    while num != 0:
        num = num % bin(num).count("1")
        ans += 1
    return ans

for i in range(n-1, -1, -1):
    if x[n - 1 - i] == "0":
        nxt = n_after_once_popcount_add
        nxt = nxt + pow_add[i]
        nxt = nxt % pop_cnt_add
        print(f(nxt) + 1)
    if x[n - 1 - i] == "1":
        if pop_cnt_sub != 0:
            nxt = n_after_once_popcount_sub
            nxt = nxt - pow_sub[i]
            nxt = nxt % pop_cnt_sub
            print(f(nxt) + 1)
        else:
            print(0)