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: Wrong Answer

Solution code:
# n = 2*10**5
# X = "10"*10**5
n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)
else:
    amari_cnt_m = 0

dp = []
for d in range(n):
    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (c - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = -1
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 2
    while True:
        c = bin(n).count("1")
        if n%c == 0:
            break
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
# print(math.log(2*10**5))

n = int(input())
x = input()
z = 0
for i in range(n):
    z += 2**(n-i-1)*int(x[i])
num_1 = x.count("1")
list_num_1 = [0] * (2*10**5+1)
# list_num_1[0] = 1
for i in range(1, 2*10**5+1):
    list_num_1[i] = int(math.log2(i)) + 1
# print(list_num_1[0:10])
for i in range(n):
    if x[i] == "0":
        tmp_num_1 = num_1 + 1
        tmp_z = 2**(n-i-1) + z
    elif x[i] == "1":
        tmp_num_1 = num_1 - 1
        tmp_z = -2**(n-i-1) + z
    counter = 0
    while tmp_z > 0:
        tmp_z = tmp_z % tmp_num_1
        tmp_num_1 = list_num_1[tmp_z]
        counter += 1
    print(counter)

Submission status: Wrong Answer

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

two_times = [1, 2, 4, 6, 8, 10, 12, 16]
three_times = [3, 5, 7, 9, 11, 13, 14, 17]
one_cnt = x.count("1")

for i in range(n):
    tmp = list(x)
    tmp_cnt = one_cnt
    num = int("".join(tmp), 2)
    if tmp[i] == "0":
        tmp_cnt += 1
        num += 2 ** (n - i - 1)
    else:
        tmp_cnt -= 1
        num -= 2 ** (n - i - 1)
    if num == 0:
        print(0)
    elif num % tmp_cnt in two_times:
        print(2)
    elif num % tmp_cnt in three_times:
        print(3)
    elif num % tmp_cnt == 0:
        print(1)
    else:
        print(4)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
X = input()
    
x1 = 0
for i in X:
    if i == '1':
        x1 += 1

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        tmp2 = -1
    else:
        tmp = (1<<(N-i-1))
        tmp2 = 1
    
    n = int(X, 2) + tmp
    if n == 0:
        print(1)
        exit()
    n = n % (x1 + tmp2)
    cnt = 1
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n = n % c
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
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

DP = [0]*(N+1)
for i in range(1,N+1):
    DP[i] = DP[i%popcount(i)]+1
X_ = int(X,2)
first_cnt = popcount(X_)
for i in range(N):
    tmp = X_
    cnt = first_cnt
    if X[i] == "0":
        tmp += 2**(N-1-i)
        cnt += 1
    else:
        tmp -= 2**(N-1-i)
        cnt -= 1
    if tmp == 0:
        print("0")
        continue
    print(DP[tmp%cnt]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x + 2 ** i
    else:
        y= x - 2 ** i
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)

Submission status: Wrong Answer

Solution code:
def count1(n):
    nx=bin(n)
    return nx.count('1')

N=int(input())
X=input()
'''for i in range(N):
    Ni2=X
    if X[i]=='0':
        Ni2=X[:i]+'1'+X[(i+1):] #文字列は変更できない
    else:
        Ni2=X[:i]+'0'+X[(i+1):]
    Ni=int(Ni2,2)
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)'''

Nx=int(X,2)
for i in range(N):
    if X[i]=='0':
        Ni=Nx+2**(len(X)-i-1)*2 #文字列は変更できない
    else:
        Ni=Nx-2**(len(X)-i-1)*2
    ans=0
    #print(Ni)
    while Ni!=0:
        Ni=Ni%count1(Ni)
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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
def main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    dd[0] = 0
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if N == 1:
        if X == '1':
            print(0)
            return 0
        else:
            print(1)
            return 1
    if x1 == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if xn1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Wrong Answer

Solution code:
def toggle(num, n):
    return num ^ (1 << n)
  
def f(n):
    ret = 0
    while True:
        popcount = sum(list(map(int,bin(n)[2:])))
        if popcount ==0:
            break
        n = n%popcount
        ret += 1
        if n==0:
            return ret
N = int(input())
s = input()
X = int('0b'+s,0)
for i in range(N):
    tmp = toggle(X,N-(i+1))
    print(f(tmp))

Submission status: Wrong Answer

Solution code:

n=int(input())
x=input()


def popcount(n):
  num=list(bin(n)[2:])
  num = [int(s) for s in num]
  return sum(num)

n_dic={1:1,2:1}

def f(first_n):
  i=0
  n=first_n
  while not n==0:
    if n in n_dic:
      n_dic[first_n]=n_dic[n]+i
      return n_dic[n]+i
    else:
      n = n % popcount(n)
      i+=1
  return i

for i in range(1,n+1):
  if x[i-1]=="0":
    tmp="1"
  else:
    tmp="0"
  X="0b"+x[:i-1]+tmp+x[i:]
  X=int(X,2)
  print(f(X))
print(n_dic)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math

memo = dict()
def main():
    n = int(input())
    x = input().rstrip()
    for i in range(n):
        tmp = x[:]
        tmp = list(tmp)
        if tmp[i] == '0':
            tmp[i] = '1'
        else:
            tmp[i] = '0'
        tmp = "".join(tmp)
        # print('tmp', tmp)
        print(fn(int(tmp, 2)))

def fn(x):
    global memo
    # print('x',x)
    bin_x = bin(x)
    if x == 0:
        return 0
    try:
        return memo[x]
    except KeyError:
        pass
    ans = 1
    c = x % bin_x.count('1')
    while c != 0:
        x = c
        bin_x = bin(x)
        c = x % bin_x.count('1')
        ans += 1
    memo[x] = ans
    return ans

if __name__ == '__main__':
    main()
    # print(fn(1))

Submission status: Wrong Answer

Solution code:
n= int(input())

ans_count = [-1 for _ in range(n)]

for i in range(1,n+1):
    b = bin(i)
    b=list(b)
    a = b.count("1")
    f = i%a
    if f == 0:
        ans_count[i-1]=1
    else:
        ans_count[i-1] = ans_count[f-1]+1

ans_count = [0]+ ans_count


inp = input()
x = list(inp)

org = int(inp, 2)
if "1" in x:      
    l = x.count("1")
else:
    l = 0

d = {}
for i in range(n+1):
    d[i]=ans_count[i]




for i in range(n):
    a = x[i]
    print(0)
#     if a=="0":
#         N = org+(2**(n-i-1))
#         m= N%(l+1)
#         print(d[m]+1)
#     else:
#         if l ==1:
#             print(0)
#         else:
#             N = org-(2**(n-i-1))
#             m=N%(l-1)
#             print(d[m]+1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda:sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**8)

def solve(k, cnt, Ans):
    S = str(bin(k)).count("1")
    if S == 0:
        return 1
    L = k % S
    if L < len(Ans)+1:
        return Ans[L]
    elif L == 0:
        return 1
    cnt += solve(L,cnt, Ans)
    return cnt 

N = int(input())
P = input()
I = P.count("1")
Df = int(P,2)
Ans = [1]

for i in range(1, I+1):
    cnt = 1
    Ans.append(solve(i, cnt, Ans)+1)
#print(Ans)

for i in range(N-1):
    if P[i] == "1":
        tmp = Df - 2**(N-i-1)
        cur = I - 1
    else:
        tmp = Df + 2**(N-i-1)
        cur = I + 1 
    if cur == 0:
        print(1)
        continue
    print(Ans[tmp%cur])
    #print(solve(tmp,cnt))

if P[N-1] == "1":
    tmp = Df - 1
    cur = I - 1
else:
    tmp = Df + 1
    cur = I + 1
if cur == 0:
    print(1)
else:
    print(Ans[tmp%cur])
#print(solve(N,cnt))

Submission status: Wrong Answer

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

memo = [0]*n
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
for i in range(n):
    if x[i] == "1":
        amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
        amariStaticB += pow(2, n-i-1, popcnt+1)
amariStaticA %= max(1, popcnt-1)
amariStaticB %= popcnt+1

for i in range(n):
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        popcnt = bin(memo[i]).count("1")
        memo[i] %= max(1, popcnt)
        cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            break


for anss in ans:
    print(anss)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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
def main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    dd[0] = 0
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if N == 1:
        if X == '1':
            return 0
        else:
            return 1
    if x1 == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if xn1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    X = [None] * N
    l = list(input())
    Xc = 0
    for i in range(N):
        X[i] = int(l[i])
        Xc += X[i]
    if Xc == 1:
        print(1)
        exit()

    ans1 = 0
    ans2 = 0
    for j in range(N):
        if X[j]==1:
            ans1 += pow(2,N-1-j,Xc+1)
            ans2 += pow(2,N-1-j,Xc-1)
    ans1 %= Xc+1
    ans2 %= Xc-1

    for i in range(N):
        if X[i]==0:# 0->1
            ans = (ans1 + pow(2,N-1-i)) % (Xc+1)
        else:# 1-> 0
            ans = (ans2 - pow(2,N-1-i)) % (Xc-1)
        count = 1
        while ans > 0:
            tmp = str(bin(ans)).count('1')
            ans %= tmp
            count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def dfs(n):
    s = str(format(n, "b"))
    c = s.count("1")
    return l[n % c] + 1
n = int(input())
x = input()
xi = int(x, 2)
c = x.count("1")
l = [0]
for i in range(1, c + 2):
    l.append(dfs(i))
for i in range(n):
    k = 0
    if x[i] == "1":
        m = xi - pow(2, n - i - 1)
        c2 = c - 1
    else:
        m = xi + pow(2, n - i - 1)
        c2 = c + 1
    if m > c2:
        if m % c2 == 0:
            print(1)
        else:
            print(l[m % c2] + 1)
    else:
        if m == 0:
            print(1)
        else:
            print(l[m])

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
times = {}
times[0] = 0

for i in range(1,200000):
  bi = format(i, 'b')
  arr = list(map(int, bi))
  sbi = sum(arr)
  if i%sbi == 0:
    times[i] = 1
  else:
    times[i] = 1+times[i%sbi]
    
arr = list(map(int, X))
sbX = sum(arr)
X10 = int(X,2)
mo = [1,-1]
if sbX-1 == 0:
  mo2 = [X10%(sbX+1),X10]
else:
  mo2 = [X10%(sbX+1),X10%(sbX-1)]

for i in range(N):
  waru = sbX+mo[int(X[i])]
  if waru == 0:
    print(0)
  else:
    print(times[(pow(2,(N-i-1),waru)+mo2[int(X[i])])%waru]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
X = input()
    
x1 = 0
for i in X:
    if i == '1':
        x1 += 1

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        tmp2 = -1
    else:
        tmp = (1<<(N-i-1))
        tmp2 = 1
    
    n = int(X, 2) + tmp
    if n == 0:
        print(0)
        exit()
    n = n % (x1 + tmp2)
    cnt = 1
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n = n % c
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if (X[i] == '1') and (cnt != 1):
        bins = (base_m1 - 2 ** (N - i - 1)) % (cnt - 1)
        nc = cnt - 1
    else:
        bins = (base_p1 + 2 ** (N - i - 1)) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            print(c[i])
            break
        n = bins % nc
        c[i] += 1
        if n == 0:
            print(c[i])
            break

        bins = n
        nc = bin(n).count('1')

Submission status: Wrong Answer

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

memo = [0]*n
ans = [-1]*n
popcnt = 0

for i in range(n):
    if x[i] == "1":
        popcnt += 1

amariStaticA = 0
amariStaticB = 0
for i in range(n):
    if x[i] == "1":
        amariStaticA += pow(2, n-i-1, max(1, popcnt-1))
        amariStaticB += pow(2, n-i-1, popcnt+1)
amariStaticA %= max(1, popcnt-1)
amariStaticB %= popcnt+1

for i in range(n):
    amari = 0
    if x[i] == "0":
        amari = amariStaticB + pow(2, n-i-1, popcnt+1)
        amari %= popcnt+1
    else:
        amari = amariStaticA - pow(2, n-i-1, max(1, popcnt-1))
        amari %= max(1, popcnt-1)
    if amari == 0:
        ans[i] = 1
    else:
        memo[i] = amari

for i in range(len(memo)):
    cnt = 1
    firstMemo = copy.deepcopy(memo[i])
    while memo[i] != 0:
        popcnt = bin(memo[i]).count("1")
        memo[i] %= max(1, popcnt)
        cnt += 1
        if memo[i] == 0:
            ans[i] = cnt
            break


for anss in ans:
    print(anss)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(input(), 2)
m = [-1]
p = [-1]
# したからi番目を反転
def reverse_x(i,x):
    a = 1<<i
    b = x^a
    return b
def f(n):
    def popcount(n):
        c = bin(n).count("1")
        return c
    count = 0
    if popcount(n) in m:
        count = p[m.index(popcount(n))]
        n = 0
    else:
        m.append(popcount(n))
    while n != 0:
        n = n % popcount(n)
        count += 1
    p.append(count)
    return count
for i in range(N):
    print(f(reverse_x(N-i-1,X)))

Submission status: Wrong Answer

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

def f(a):
  flg=0
  count=0
  while flg==0:
    n=bin(a)
    ncount=n.count('1')
    if ncount == 0:
      a=0
    else:
      a=a % ncount
    count+=1
    if a==0:
      flg=1
  return(count)

for i in range(N):
  if X[i]=='0':
    X[i]='1'
  else:
    X[i]='0'
  
  a=''.join(X)
  
  #print(a)
  
  tmp=int(a,2)
  print(f(tmp))
  
  X=list(a)
  
  if X[i]=='0':
    X[i]='1'
  else:
    X[i]='0'

Submission status: Wrong Answer

Solution code:
N = int(input())
X ='0b'+ input()
def popcount(n): #10進数をもらって10進数を返す
    n2 = bin(n)
    counter_1 = 0
    for i in range(len(str(n2))):
        
        if str(n2)[i] == '1':
            counter_1 +=  1
    return counter_1

def anything(n): #2進数をもらってcounter 10進数を返す
    #print(n)
    n10 = int(n,0)
    counter = 0
    while n10 > 0:
        #print('popcount(n10)', popcount(n10))
        n10 = n10 % popcount(n10)
        counter +=1
        #print(n10)
    return counter
#print(anything(n))

line = []
for i in range(N):
    x = X
    if x[i+2] == '0':
        x = x[:i+2] +'1' +  x[i+3:]
    else:
        x = x[:i+2] +'0' +  x[i+3:]
        
    line.append(x)
for i in line:
    print(i,anything(i))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    if cnt == 1:
        ans = []
        i = 0
        for d in reversed(X):
            if d:
                ans.append(0)
                continue
            if i == 0 or X[-1]:
                ans.append(2)
            else:
                ans.append(1)

        ans.reverse()

        print(*ans, sep='\n')
        return

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        t_1_0 = t_1_0 * 2 % (cnt - 1)
        pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
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
def main():
    N = int(input())
    X = input()
    d = {}
    dd = {}
    x1 = X.count('1')
    xn = int(X, 2)
    dd[0] = 0
    def hoge(i):
        if i in dd:
            return dd[i]
        if i not in d:
            j = popcount(i)
            d[i] = i % j
            if d[i] == 0:
                dd[i] = 1
            else:
                dd[i] = 1 + hoge(d[i])
        return dd[i]
    if x1 == 1:
        xn1 = 0
    else:
        xn1 = xn % (x1-1)
    xn2 = xn % (x1 + 1)
    for i in range(N):
        if X[i] == '1':
            t = xn1
            if xn1 == 0:
                print(0)
                continue
            t -= pow(2, N-1-i, x1-1)
            t %= (x1-1)
        else:
            t = xn2
            t += pow(2, N-1-i, x1+1)
            t %= (x1 + 1)
        if t == 0:
            print(1)
        else:
            print(1 + hoge(t))
main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(readline().rstrip().decode('utf-8'))


res = lst1.copy()
res = "".join(res)
ct = res.count("1")
res = int(res,2)
if ct == 0:
    for i in range(n):
        print(0)
    exit()
if ct == 1:
    amari_of_m = -1
else:
    amari_of_m = res%(ct-1)
amari_of_p = res%(ct+1)

def pow(n,p,mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def func(res):
    ans = 1
    while True:
        ct = 0
        for i in range(len(bin(res))):
            if res>>i&1:
                ct += 1
        if res%ct == 0:
            print(ans+1)
            return
        else:
            res %= ct
            ans += 1

for i in range(n):
    if lst1[i] == "1" and amari_of_m == -1:
        print(1)
        continue
    resres = pow(2,n-i-1,ct-1) if lst1[i] == "1" else pow(2,n-i-1,ct+1)
    if lst1[i] == "1":
        resres = amari_of_m - resres
        resres %= ct-1
    else:
        resres = amari_of_p + resres
        resres %= ct+1
    if not resres:
        print(1)
    else:
        func(resres)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

N = int(input())
X = input()
Ret = []
d = {}

for i in range(N):
    x = ''
    if X[i] == '0': x = '1'
    else: x = '0'
    b = ''
    if i < N-1:
        b = '0b' + X[:i] + x + X[i+1:]
    else:
        b = '0b' + X[:i] + x
    a = int(b, 2)
    b2 = b
    cnt = 0
#    print('---')
    while True:
        cnt += 1
        a2 = int(b2, 2)
#        print(b, a2, cnt)
        if a2 in d:
            if d[a2] == 0:
                Ret.append(cnt)
                break
            b2 = bin(d[a2])
            continue

        c = b2.count('1')
        if c != 0:
            w = a2%c
        else:
            w = 0
        b2 = bin(w)
        d[a2] = w

        if w == 0:
            Ret.append(cnt)
            break
        
for r in Ret:
    print(r)

Submission status: Wrong Answer

Solution code:
def flipXandTransDecimalnum(X, keta):
  #print(X)
  X=[c if not keta==i else ('1' if c=='0' else '0' )for i,c in enumerate(X) ]
  #print(X)
  X.reverse()
  su=0
  pop=0
  for i in range(0,len(X)):
    su+=int(X[i])*2**i
  return su
def popcount(X):
  cnt=0
  while (X > 0):
    cnt+=X%2
    X//=2
  return cnt
N=int(input())
X=input()

for i in range(len(X)):
  intX=flipXandTransDecimalnum(X,i)
  for j in range(intX):
    pop=popcount(intX)
    #print(intX,pop)
    intX = intX % pop
    if intX == 0:
      print(j+1)
      break

Submission status: Wrong Answer

Solution code:
def m():
    N = int(input())
    X = input()
    R = list(reversed(X))

    memo = [0] * (N+2)
    for i in range(1, N+2):
        p = 0
        k = i
        while k != 0:
            if k % 2 == 1:
                p+=1
            k //= 2
        memo[i] = p

    def f(n):
        r = 0
        while n != 0:
            n = n % memo[n]
            r += 1
        return r
    memo2 = [0] * (N+2)
    for i in range(1, N+2):
        memo2[i] = memo[i]


    total = 0
    for i in range(N):
        total += int(R[i]) * pow(2, i)

    base = X.count('1')
    for i in range(N):
        ans = 0
        if X[i] == '1':
            tmp = total - pow(2, N - 1 - i)
            if (base-1) == 0:
                print(0)
                continue
            tmp %= (base - 1)
            ans = memo2[tmp] + 1
        else:
            tmp = total + pow(2, N - 1 - i)
            tmp %= (base + 1)
            ans = memo2[tmp] + 1
        print(ans)


m()

Submission status: Wrong Answer

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

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

lst = [None] * (10 ** 5 + 1)
for i in range(n):
    y = x[:]
    if x[i] == "1":
        y[i] = "0"
        z = "".join(y)
        z = int(z, 2)
        if z == 0:
            print(1)
        else:
            z %= (cnt - 1)
            if z == 0:
                print(1)
            else:
                w = z
                ans = 1
                while z > 0:
                    if lst[z]:
                        print(lst[z])
                        break
                    z %= popcount(z)
                    ans += 1
                print(ans)
                lst[w] = ans
    else:
        y[i] = "1"
        z = "".join(y)
        z = int(z, 2)
        z %= (cnt + 1)
        if z == 0:
            print(1)
        else:
            if z == 0:
                print(1)
            else:
                w = z
                ans = 1
                while z > 0:
                    if lst[z]:
                        print(lst[z])
                        break
                    z %= popcount(z)
                    ans += 1
                print(ans)
                lst[w] = ans

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
x = list(input())
d = defaultdict(int)

for i in range(n):
    tmp = x[i]
    if tmp:
        x[i] = '0'
    else:
        x[i] = '1'
    num = int(''.join(x), 2)
    res = 0
    arr = []
    while num:
        if d[num]:
            res += d[num]
            break
        cnt = bin(num).count('1')
        num %= cnt
        res += 1
        arr.append(num)
    print(res)
    for a in arr:
        res -= 1
        d[a] = res

    x[i] = tmp

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
xx=x.count('1')
xx2=int(x,2)
l=[0]
for i in range(1,xx+2):
    i1=str(bin(i)).count('1')
    num=0
    while i!=0:
        i%=i1
        i1=str(bin(i)).count('1')
        num+=1
    l.append(num)
print(l)
k=2**n
for i in range(n):
    k//=2
    if x[i]=='0':
        xxx=xx+1
        xxx2=xx2+k
    else:
        xxx=xx-1
        xxx2=xx2-k
    if xxx2==0:
        print(0)
    elif xxx2%xxx==0:
        print(1)
    elif xxx2<=xx+1:
        print(l[xxx2])
    else:
        print(l[xxx2%xxx]+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
# N = 2 * 10 ** 5
# X = "10"*(10**5)
cnt = X.count('1')

base = int(X, 2)
if cnt == 1:
    base_m1 = 0
else:
    base_m1 = base % (cnt - 1)
base_p1 = base % (cnt + 1)

c = dict()
for i in range(N):

    if (X[i] == '1') and (cnt != 1):
        bins = base_m1 - 2 ** (N - i - 1) % (cnt - 1)
        nc = cnt - 1
    else:
        bins = base_p1 + 2 ** (N - i - 1) % (cnt + 1)
        nc = cnt + 1

    c[i] = 0
    while True:
        if nc == 0:
            print(c[i])
            break
        n = bins % nc
        c[i] += 1
        if n == 0:
            print(c[i])
            break

        bins = n
        nc = bin(n).count('1')

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
X = input()
    
x1 = 0
for i in X:
    if i == '1':
        x1 += 1

for i in range(N):
    if X[i] == '1':
        tmp = - (1<<(N-i-1))
        tmp2 = -1
    else:
        tmp = (1<<(N-i-1))
        tmp2 = 1
    
    n = int(X, 2) + tmp
    if n == 0:
        print(0)
        exit()
    n %= x1 + tmp2
    cnt = 1
    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n %= c
        cnt += 1
    print(cnt)