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:

a = int(input())
b = input()

@lru_cache(maxsize=None)
def func(c):
    c = [int(z) for z in c]
    x = int(sum(c))
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(c):
        nsum += n * i
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])




for i in range(a):
    ran = list(b)
    ran[i] = "0" if ran[i] == "1" else "1"
    c = "".join(ran)
    print(func(c))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n=int(input())
xs=input()
#xk=list(map(int,list(xs)))
xj=xs.count("1")

x=int(xs,2)

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

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
#    print(i,xi,"pxi",pxi)
    if xi==0:
        print(0)
    else:
#        print("i",i,"xi",xi,"pxi",pxi)
        xi=xi%pxi
#        print("--i",i,"xi",xi,"pxi",pxi)
        if xi==0:
            print(1)
        else:
#            print("i",i,"xi",xi,"pxi",pxi)
#            print(i,pxi,xi,popcount(xi),xi%popcount(xi))
            icnt=1
            while xi>0:
                icnt+=1
#                print(i,pxi,xi,popcount(xi),xi%popcount(xi))
                xi=xi%popcount(xi)
            print(icnt)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
flag1 = 0
flag0 = 0


def popcount(n: int):
    bin_n = bin(n)
    return str(bin_n).count('1')


popcount_X = popcount(int(X, 2))

for i in range(N):
    count = 0
    if X[i] == '1':
        tmp = int(X)
        tmp -= 10 ** (N - i - 1)
        flag1 += 1
    else:
        tmp = int(X)
        tmp += 10 ** (N - i - 1)
        flag0 += 1
    tmp = int(str(tmp), 2)

    while True:
        if tmp == 0:
            print(count)
            break
        elif flag1:
            count += 1
            tmp = tmp % (popcount_X-1)
            flag1 = 0
        elif flag0:
            count += 1
            tmp = tmp % (popcount_X+1)
            flag0 = 0
        else:
            count += 1
            tmp = tmp % popcount(tmp)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    if count > 0:
      now *= 2
      nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    
    if count >= 2:
      nowm *= 2
      nowm %= (count - 1)
  
  else:
    if count >= 1:
      now %= count
    nowp %= (count + 1)
    if count >= 2:
      nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    if count > 0:
      num += now
      num %= count
    nump += nowp
    nump %= count + 1
    if count > 1:
      numm += nowm
      numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
  if count == 0:
    nextn[i] = 0
  else:  
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      if count == 2:
        nextn[i] = 0
      else:
        a = numm - x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1 # 0になりうる
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

# f の前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i // 2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

# pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i - 1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i - 1] * 2 % zero_pop_count

# n-1, n-2, ..., 0
for i in range(n-1, -1, -1):
    if x[n-i-1] == '1':
        if one_pop_count != 0:
            nxt = one_mod
        # nxt -= pow(2, i, one_pop_count)
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f(nxt) + 1)
        else:
            print(0)
    elif x[n-i-1] == '1':
        nxt = zero_mod
        # nxt += pow(2, i, zero_pop_count)
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f(nxt) + 1)

Submission status: Runtime Error

Solution code:
N = int(input())
X = str(input())
count = X.count("1")
num, nump, numm = 0, 0, 0
now, nowp, nowm = 1, 1, 1

xx = [0] * N
x_plus = [0] * N
x_minus = [0] * N
for i in range(1, N + 1):
  if i != 1:
    if count > 0:
      now *= 2
      nowp *= 2
    
    now %= count
    nowp %= (count + 1)
    
    if count >= 2:
      nowm *= 2
      nowm %= (count - 1)
  
  else:
    if count >= 1:
      now %= count
    nowp %= (count + 1)
    if count >= 2:
      nowm %= (count - 1) 
  xx[i - 1] = now
  x_plus[i - 1] = nowp
  x_minus[i - 1] = nowm
  if X[-i] == "1":
    if count > 0:
      num += now
      num %= count
    nump += nowp
    nump %= count + 1
    if count > 1:
      numm += nowm
      numm %= count - 1
    
#print(num, xx, x_plus, x_minus)    

nextn = [0] * N
#ans = [1] * N
for i in range(N):
  if count == 0:
    nextn[i] = 0
  else:  
    if X[i] == "0":
      a = nump + x_plus[N - 1 - i]
      b = count + 1
      #print(a, b)
      nextn[i] = a % b
    else:
      if count == 2:
        nextn[i] = 0
      else:
        a = numm + x_minus[N - 1 - i]
        b = count - 1
        nextn[i] = a % b
        
#print(nextn)    
for i in range(N):
  if nextn[i] == 0:
    print("1")
  else:
    nownow = nextn[i]
    ans = 1
    while nownow != 0:
      alpha = bin(nownow)[2:]
      beta = str(alpha).count("1")
      nownow %= beta
      ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(input())
def str2int(z):
  flag=1
  a=0
  for i in reversed(x):
    if i=='1':a+=flag
    flag*=2
  return a

popc=x.count('1')
x=str2int(x)

cc=[]
for i in range(n):
  if ((x>>i)&1):
    mod=(x-2**i)%(popc-1)
  else:mod=(x+2**i)%(popc+1)
  #print('mod : %s'%mod)
  cnt=1
  while mod!=0:
    pp=bin(mod).count("1")
    mod%=pp
    cnt+=1
  cc.append(cnt)
  
for c in reversed(cc):
  print(c)

Submission status: Runtime Error

Solution code:
def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    
    s0 = X_10 % r0 
    s1 = X_10 % r1 

    for i in range(N):
        if X[i] == '0':
            ans.append(f((s1 + pow(2,N-1-i,r1)) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f((s0 - pow(2,N-1-i,r0)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    
    s0 = X_10 % r0 
    s1 = X_10 % r1 

    for i in range(N):
        if X[i] == '0':
            ans.append(f(s1 + pow(2,N-1-i) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f(s0 - pow(2,N-1-i) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
X = int(input())

def popcount(n,x):
    count = 0
    for i in range(n):
        if (x>>i) & 1 == 1:
            count += 1
    return(count)


for i in range(N):
    prenum = str(X)
    num = prenum.zfill(N)
    if num[i] == '0':
        num = num[:i] + '1' + num[i+1:]
    else:
        num = num[:i] + '0' + num[i+1:]
    
    count = 0
    tennum = int(num,2)
    result = 1
    while True:
        if result == 0:
            break
        
        popc = popcount(N,tennum)
        result = tennum%popc
        
        tennum = result
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
def solve():
    N = int(input())
    X = input()
    X_10 = int(X,2)

    r = X.count("1")
    r0 = r-1
    r1 = r+1
    ans = []
    
    s1 = X_10 % r1 
    s0 = X_10 % r0 
    for i in range(N):
        if X[i] == '0':
            ans.append(f((s1 + pow(2,N-1-i)) % r1))
        else:
            if r == 1:
                ans.append(0)
            else:
                ans.append(f((s0 - pow(2,N-1-i)) % r0))
    
    print(*ans, sep='\n')

def f(N):
    cnt = 1
    while N != 0:
        N = N % popcount(N)
        cnt += 1
    
    return cnt

def popcount(N):
    b = bin(N)
    cnt = 0
    for i in range(2,len(b)):
        if b[i] == '1':
            cnt += 1

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    x0 = x00 % bn0
    xi = x0 - b * pow(2,N-1-i,bn0) + bn * pow(2,N-1-i,bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1')
        num = num % p
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
N = int(input())
X = input()
X10 = int('0b'+X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Runtime Error

Solution code:
N = int(input())
X = input()
x = int(X, 2)
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
zero_mod = x % zero_pop
one_mod = x % one_pop

def popcount(n):
    return bin(n).count('1')
def f_count(n):
    ans = 0
    while n != 0:
        n %= popcount(n)
        ans += 1
    return ans
for i in range(N):
    if X[i] == '1' and X.count('1') == 1:
        print(0)
        continue
    if X[i] == '1':
        x = (one_mod - 2**(N-1 -i) % one_pop) % one_pop
    else:
        x = (2**(N-1 -i) % zero_pop + zero_mod) % zero_pop
    print(f_count(x) + 1)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
N = int(input())
X = input()
X10 = int('0b'+X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
import sys
input = sys.stdin.readline
 
N = int(input())
X = input().rstrip()
X10 = int('0b'+X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
import sys
input = sys.stdin.readline
 
N = int(input())
X = list(input().rstrip())
X10 = int('0b'+"".join(X),2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
X = list(input().rstrip())
X10 = int('0b'+"".join(X),2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        #print(bin(X10),bin(a),X10,a,amari)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
        #print(bin(X10),bin(a),X10,a,amari)
    nc = amari
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
import sys
input = sys.stdin.readline
 
 
def popcount(n):
    bin_str = bin(n)
    cou1 = bin_str.count('1')
    return cou1
 
def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co
 
N = int(input())
X = list(input().rstrip())
X10 = int('0b'+"".join(X),2)
X10_num1 = popcount(X10)
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        #print(bin(X10),bin(a),X10,a,amari)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
        #print(bin(X10),bin(a),X10,a,amari)

    if a ==0:
        co = 0
    else:
        co = count(amari)+1
    print(co)

Submission status: Runtime Error

Solution code:
#AIsing2020 d
 
import sys,math,collections,itertools,copy
input = sys.stdin.readline
 
 
def popcount(n):
    bin_str = bin(n)
    cou1 = bin_str.count('1')
    return cou1
 
def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co
 
N = int(input())
X = list(input().rstrip())
X10 = int('0b'+"".join(X),2)
X10_num1 = popcount(X10)
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1)


for i in range(N,0,-1):
    a = X10
    if a>>(i-1) & 1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        #print(bin(X10),bin(a),X10,a,amari)
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
        #print(bin(X10),bin(a),X10,a,amari)

    if a ==0:
        co = 0
    else:
        co = count(amari)+1
    print(co)

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)



calc_dict = {i:-1 for i in range(100000)}
res_dict =  {i:-1 for i in range(100000)}

for i in range(1, 100000):
    if calc_dict[i]==-1:
        calc_dict[i] = bin(i).count("1")

    res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    while temp!=0:

        if temp in res_dict:
            return count+res_dict[temp]
        
        if temp in calc_dict:
            calc_dict[temp]=bin(temp).count("1")
        bits = calc_dict[temp]
            
        temp = temp%bits
        count+=1

    return count

for i in range(N):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = input()
    XINT = int(X,2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N


    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    
    bit = 1
    p = XINT % (cnt+1)
    m = 0
    if cnt != 1 :
        m = XINT % (cnt-1)
    pmod = 1
    mmod = 1
    for i in range(N):
        if (cnt !=1):
            ANS[i] = 1
            if (X[N-i-1] == '0'):
                TEMP[i] = (p + pmod) % (cnt+1)
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

import math
# 最初にpopcount用のリストを作成する，そもそも2**(10**5)だから圧倒的に範囲が足らなかった
#L = [0 for i in range(int(math.log(N,2))+10)]
#for i in range(int(math.log(N,2))+10):
#    bi = list(str(bin(i)))
#    bi = bi[1:]
#    L[i] = bi.count('1')

# i番目のビットを反転させて,
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    x0 = x00 % bn0
    xi = x0 - b * pow(2,N-1-i,bn0) + bn * pow(2,N-1-i,bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        bi = list(str(bin(num)))
        bi = bi[2:]
        st = ''.join(bi)
        if st in dic:
            bic = dic[st]
        else:
            bic = bi.count('1')
            dic[st] = bic
        num = num % bic
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = input()
    XINT = int(X,2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N


    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    
    bit = 1
    p = XINT % (cnt+1)
    m = 0
    if cnt != 1 :
        m = XINT % (cnt-1)
    pmod = 1
    mmod = 1
    for i in range(N):
        if not (cnt ==1 and X[N-i-1]=='1'):
            ANS[i] = 1
            if (X[N-i-1] == '0'):
                TEMP[i] = (p + pmod) % (cnt+1)
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = input()
    XINT = int(X,2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N


    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    
    bit = 1
    p = XINT % (cnt+1)
    m = XINT % (cnt-1)
    pmod = 1
    mmod = 1
    for i in range(N):
        if not (cnt ==1 and X[N-i-1]=='1'):
            ANS[i] = 1
            if (X[N-i-1] == '0'):
                TEMP[i] = (p + pmod) % (cnt+1)
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
X= input()

def popcount(n):
    a = list(str(bin(n)))
    return sum([int(i) for i in a[2:]])

waru = sum([int(x) for x in (list(X))])
X10 = int(X,2)

for i in range(N):
    ans = 1
    if X[i] == '1':
        Xe = X10 - (1 << (N-i-1))
        warue = waru-1
    else:
        Xe = X10 + (1 << (N-i-1))
        warue = waru+1
    # print(Xe,warue)
    Xe= Xe % warue
    if Xe != 0:
        for _ in range(10):
            Xe = Xe % popcount(Xe)
            ans += 1
            if Xe ==0:
                break

    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = int(input(),2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N


    cnt = count_ones_by_bitmask(X)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return

    p = X % (cnt+1)
    m = X % (cnt-1)
    pmod = 1 % (cnt+1)
    mmod = 1 % (cnt-1)
    bit = 1
    for i in range(N):
        L = (X^bit)
        if L!=0:
            ANS[i] = 1
            if (X & bit == 0):
                TEMP[i] = (p + pmod) % (cnt+1)
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        bit = bit<<1
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        if n > x:
            n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum)
    nsum = cans.count("1")
    if nsum == 0:
        return 1
    else:
        return 1 + func(cans[2:])

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    print(str(func("".join(s))))

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1)
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)

def mods(temp, count):
    count+=1
    while temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")
            
        temp = temp%bits
        count+=1

    return count

for i in range(len(S)):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1

    cnt = count_ones_by_bitmask(X)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return

    p = X % (cnt+1)
    m = X % (cnt-1)
    pmod = 1 % (cnt+1)
    mmod = 1 % (cnt-1)
    for i in range(N):
        LIST.append(X^bit)
        if LIST[i]!=0:
            ANS[i] = 1
            if (X & bit == 0):
                TEMP[i] = (p + pmod) % (cnt+1)
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        bit = bit<<1
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])




def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys


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


def main():
    N = int(sys.stdin.readline().rstrip())
    X = sys.stdin.readline().rstrip()

    Xdec = int(X, 2)

    # X がゼロなら終了
    if Xdec == 0:
        print(0)
        return

    # 1回目の演算用
    md = popcount(Xdec)
    md_p, md_m = md + 1, md - 1

    tmp_p = Xdec % md_p
    if md_m == 0:
        tmp_m = Xdec % md_m

    for i in range(0, N, 1):
        if X[i] == "1":  # 1->0
            if md_m == 0:
                print(0)
            x_m = pow(2, (N - 1 - i), md_m)
            tmp = (tmp_m - x_m) % md_m

        if X[i] == "0":  # 0->1
            x_p = pow(2, (N - 1 - i), md_p)
            tmp = (tmp_p + x_p) % md_p

        cnt = 1
        while tmp:

            tmp = tmp % popcount(tmp)
            cnt += 1

        print(cnt)


main()

Submission status: Runtime Error

Solution code:
a = int(input())
b = input()

def func(c):
    x = c.count("1")
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        if c[i] == "1":
            nsum += n
            if n > x:
                n = n % x
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum))

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

Submission status: Runtime Error

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


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


def main():
    N = int(sys.stdin.readline().rstrip())
    X = sys.stdin.readline().rstrip()

    Xdec = int(X, 2)

    # X がゼロなら終了
    if Xdec == 0:
        print(0)
        return

    # 1回目の演算用
    md = X.count("1")
    md_p, md_m = md + 1, md - 1
    tmp_p = Xdec % md_p
    tmp_m = Xdec % md_m

    for i in range(0, N, 1):
        if X[i] == "1":
            x_m = pow(2, (N - 1 - i), md_m)
            tmp = (tmp_m - x_m) % md_m

        if X[i] == "0":
            x_p = pow(2, (N - 1 - i), md_p)
            tmp = (tmp_p + x_p) % md_p

        cnt = 1
        while tmp:

            tmp = tmp % popcount(tmp)
            cnt += 1

        print(cnt)


main()