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:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
    break
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Submission status: Wrong Answer

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

memo = [-1] * (n+10)
def calc(x):
    if(memo[x] != -1):
        return memo[x]
    if(x==0):
        return 0
    cnt = 0
    x2 = x
    while(x2 > 0):
        cnt += (x2&1)
        x2 //= 2
    next = x%cnt
    memo[x] = 1 + calc(next)
    return memo[x]

cnt0 = x.count('1')
if(cnt0 == 0):
    ans = [1] * n
    print('\n'.join(map(str,ans)))
    exit()
if(cnt0==1):
    ans = [0] * n
    for i in range(n):
        ans1 = 1 + ( x[-1] == '1')
        if(x[i]=='0'):
            ans[i] = ans1
        else:
            ans[i] = 0
    print('\n'.join(map(str,ans)))
    exit()

rem_p = [0] * n
rem_m = [0] * n
rem_p[0] = 1
rem_m[0] = 1%(cnt0-1)

for i in range(1,n):
    rem_p[i] = (2*rem_p[i-1])%(cnt0+1)
    rem_m[i] = (2*rem_m[i-1])%(cnt0-1)

x_p = 0
x_m = 0
for i in range(n):
    if(x[n-1-i] == '1'):
        x_p += rem_p[i]
        x_m += rem_m[i]
x_p %= (cnt0+1)
x_m %= (cnt0-1)

ans = [0] * n
for i in range(n):
    if(x[i]=='1'):
        first = (x_m - rem_m[n-1-i])%(cnt0-1)
        ans[i] = calc(first) + 1
    else:
        first = (x_p + rem_p[n-1-i])%(cnt0+1)
        ans[i] = calc(first) + 1

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

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def getMod(_str, n, k):
    global pwrTwo
    res = 0
    for i in range(len(_str)):  
        if _str[n-i-1] == '1':  
            res += pwrTwo[i]%k
            res %= k 
    return res
def inv(i):
    if x[i] == '1':
        return '0'
    else:
        return '1'

n = inp()
pwrTwo = [0]*n
pwrTwo[0] = 1
for i in range(1,n):  
    pwrTwo[i] = pwrTwo[i-1]*2
x = list(input().strip())
tt = x.count('1')
for i in range(n):
    ctr = tt-1 if x[i]=='1' else tt+1
    x[i] = inv(i)
    no = getMod(''.join(x),n,ctr)
    ct = 1
    while no:
        k = bin(no).count('1')
        no %= k
        ct += 1
    print(ct)
    x[i] = inv(i)

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)
    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 N == 2:
        if X == '11':
            print(1)
            print(1)
            return 0
    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
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

divmemo = {}
def popcountdiv(n, onecount):
    if n in divmemo:
        return divmemo[n]
    myonecount = onecount
    if myonecount == -1:
        myonecount = bin(n).count("1")
    res = n % myonecount
    divmemo[n] = res
    return res

memo = {}
def f(n, onecount):

    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    else:
        res = f(popcountdiv(n, onecount), -1)
        memo[n] = res+1
        return 1 + res

N = int(input())
X = input()
onecount = X.count("1")
mathX = int(X, 2)
for i in range(N):
    if X[i] == "1":
        #print(X, mathX, mathX-2**(N-(i+1)))
        if mathX-2**(N-(i+1))%7 == 0:
            print(3)
        else:
            print(f(mathX-2**(N-(i+1)), onecount-1))

    else:
        #print(X, mathX, mathX+2**(N-(i+1)))
        if mathX-2**(N-(i+1))%7 == 0:
            print(3)
        else:
            print(f(mathX+2**(N-(i+1)), onecount+1))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(input())
pwa = 0
mwa = 0
kosuu = X.count("1")
def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count
def popcount(n,count):
    if n == 0:
        print(count)
    else:
        count += 1
        popcount(n % count_ones_by_bin(n),count)
if kosuu > 0:
    for i in range(N):
        if X[i] == "1":
            pwa += pow(2,N-i-1,kosuu+1)
            if kosuu > 1:
                mwa += pow(2,N-i-1,kosuu-1)
for i in range(N):
    ans = 0
    if X[i] == "1":
        kosuu -= 1
        if kosuu == 0:
            print(0)
            continue
        now = (mwa - pow(2,N-i-1,kosuu))%kosuu
        popcount(now,0)
    else:
        kosuu += 1
        now = (pwa + pow(2,N-i-1,kosuu))%kosuu
        popcount(now,0)

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
#input = sys.stdin.readline
import copy

# S=(input())
# N=int(input())
# N,K=map(int,input().split())
# ListA=list(map(int,input().split()))
# ListA.sort()#reverse=True)

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 resolve():
    
    N=int(input())
    X=(input())
    #N=200000
    #X="1"*200000

    cnt=0
    for i in range(N):
        tmprev='1'
        if(X[i]=='1'):
            tmprev='0'
        if(i==0):
            tmp=tmprev+X[i+1:]    
        elif(i==N):
            tmp=X[:i]+tmprev    
        else:
            tmp=X[:i]+tmprev+X[i+1:]

        if(i!=0 and N-i>18):
            print(cnt)
            continue
            
        orgpop=tmp.count("1")
        orgpop2=1
        shift=0
        while(True):
            orgpop2*=2
            shift+=1
            if(orgpop2>orgpop):
                break

        tmp=tmp[N-shift:]
        
        Xi=int(tmp,2)
        
        cnt=0
        first=True
        while True:
            if(Xi==0):
                print(cnt)
                break
            if(first):
                pop=orgpop
                first=False
            else:
                pop=popcount(Xi)
            Xi=Xi%pop
            cnt+=1




resolve()

Submission status: Wrong Answer

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

def count_bits(x):
    cnt = 0
    while x:
        x = x&(x-1)
        cnt += 1
    return cnt

def f(X):
    x = int(X, 2)
    cnt = 0
    while x:
        x %= count_bits(x)
        cnt += 1
    return cnt


def flip(X, i):
    a = '0' if X[i] == '1' else '0'
    return X[:i] + a + X[i+1:]

for i in range(N):
    print(f(flip(X, i)))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)

for n in range(1, N+1):
    c = pl[n-1]
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    elif c == 1:
        print(1)
    elif c == 2:
        print(2)
    else:
        print(1 + t[x%c])

Submission status: Wrong Answer

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

for i in range(0, n):
    ans = 0
    x = list(x)
    if x[i] == "1":
        x[i] = "0"
        b = a-1
    else:
        x[i] = "1"
        b = a+1
    x = "".join(x)
    xatai = int(x, 2)
    while b != 0:
        xatai = xatai % b
        b = str(xatai).count("1")
        ans += 1
    print(ans)
    x = list(x)
    if x[i] == "1":
        x[i] = "0"
        b = a-1
    else:
        x[i] = "1"
        b = a+1

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(1)
    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:
        resres = 0
    else:
        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
        if amari_of_m == -1:
            pass
        else:
            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:
N = int(input())
N = 2 * 10 ** 5
S = list(map(int,list(input())))
S = [1] * 10 ** 5 * 2
S.reverse()
r = [0 for _ in range(2 * (10 ** 5) + 100)]
p0 = [0 for _ in range(N + 10)]
q0 = 0
p1 = [0 for _ in range(N + 10)]
q1 = 0
q = S.count(1)
p0[0] = 1
p1[0] = 1

for i in range(N):
    p0[i + 1] = (p0[i] * 2) % (q + 1)
    if S[i] == 1:
        q0 += p0[i]
        q0 %= q + 1

for i in range(N):
    p1[i + 1] = (p1[i] * 2) % (q - 1)
    if S[i] == 1:
        q1 += p1[i]
        q1 %= q - 1

r[0] = 0
for i in range(1,2 * (10 ** 5)+10):
    qx = 0
    for i2 in range(22):
        if i >> i2 & 1:
            qx += 1
    r[i] = r[i % qx] + 1

for i in range(N):
    if S[N - i - 1] == 0:
        print(r[(q0 + p0[N-i-1]) % (q + 1)] + 1)
    else:
        print(r[(q1 - p1[N-i-1]) % (q - 1)] + 1)

Submission status: Wrong Answer

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    from numba import jit
    @jit(cache = True)
    def calc(x):#xは数字
        if x==0:
            return 0
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        return xn%cnt

    n=int(input())
    f=[]
    f.append(0)
    for i in range(1,2**18+1):
        f.append(f[calc(i)]+1)

    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            xx=x-2**i
            if xx==0:
                ans.append(1)
            else:
                ans.append(f[xx%(cnt-1)]+1)
        else:
            ans.append(f[(x+2**i)%(cnt+1)]+1)
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

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 == 0:
        print(0)
        exit()
    elif 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)
            ans1 %= Xc+1
            ans2 += pow(2,N-1-j,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:
import collections
N=int(input())
X=list(input())
X=list(map(int,X))
#print(X)
ans1=0
ans2=0
c=collections.Counter(X)
div=c[1]
for i in range(N):
    ans1=(ans1+X[i]*pow(2,N-i-1,div+1))%(div+1)
    if div-1!=0:
        ans2=(ans2+X[i]*pow(2,N-i-1,div-1))%(div-1)
    else:
        ans2=None
    #print(ans1)
#print(ans1,div+1)
#print(ans2,div-1)
#ここまででXについてのXのbit数、X%(Xのbit数)がわかる
for i in range(N):
    cnt = 1
    if (X[i]==0):
        num=(ans1+pow(2,N-i-1,div+1))%(div+1)
        #print(num)
    else:
        if (div-1)!=0:
            num=(ans2+div-1-pow(2,N-i-1,div-1))%(div-1)
        else:
            cnt=1
            print(cnt)
            break
        #print(num)
    while num != 0:
        di = 0
        for j in range(18):
            if (num >> j)&1 == 1:
                di = di + 1
        num = num % di
        cnt = cnt + 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)

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

M = int(2e5)
memo = [-1] * (M + 1)
memo[0] = 0

def ff(n, cnt):
    # print(n,cnt)
    if memo[n] != -1:
        # print("memo,", memo[n])
        return cnt + memo[n]
    cnt += 1
    nxt = n % popcnt(n)
    # print(n,cnt,nxt)
    if nxt == 0:
        return cnt
    ret = ff(nxt, cnt)
    memo[n] = ret
    return ret

def f(n):
    if n <= M and memo[n] != -1:
        return memo[n]
    nxt = n % popcnt(n)
    if nxt == 0:
        return 1
    return ff(nxt, 1)

# print(f(1808070))
# print(f(1808074))

# print(f(6002382))
# print(f(3905230))
# print(f(759502))
# print(f(1283790))
# print(f(2070222))
# print(f(1677006))
# print(f(1742542))
# print(f(1775310))

# print(f(1824462))
# print(f(1816270))
# print(f(1803982))
# print(f(1810126))
# print(f(1807054))
# print(f(1807566))
# print(f(1808334))
# print(f(1807950))
# print(f(1808014))
# print(f(1808110))
# print(f(1808094))
# print(f(1808070))
# print(f(1808074))
# print(f(1808076))
# print(f(1808079))
# print(f(7))
# exit(0)

n = int(input())
x = int(input(), 2)
ans = [0] * n


for i in range(n):
    tmp = x
    if (tmp >> (n-i-1)) & 1:
        tmp &= ~(1 << (n-i-1))
    else:
        tmp |= (1 << (n-i-1))
    # print("print(f({}))".format(tmp))
    ans[i] = f(tmp)

for v in ans:
    print(v)

Submission status: Wrong Answer

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

co = [0] * (N + 1)
for i in range(1,N+1):
    a = bin(i)[2:]
    cnt = a.count('1')
    nex = i % cnt
    if nex != 0:
        co[i] = nex + 1
    else:
        co[i] = 1
    
for i in range(N):
    x = X
    if x[i] == '0':
        x = x[:i] + '1' + x[i+1:]
    else:
        x = x[:i] + '0' + x[i+1:]
    num = x.count('1')
    if num == 0:
        print(0)
        break
    pop = int(x,2) % num
    ans = co[pop] + 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from typing import List, Tuple

N = int(input())
X = list(map(int, input()))


def divmod_long(bits: List[int], div: int) -> Tuple[List[int], int]:
    val = 0
    q = []
    for b in bits:
        val = val * 2 + b
        if val < div:
            q.append(0)
            continue
        else:
            q.append(1)
            val = val - div
    return q, val

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

def f(bits, div):
    cnt = 0
    q, r = divmod_long(bits, div)
    cnt += 1
    while r != 0:
        r = r % popcount_int(r)
        cnt += 1
    return cnt


popcount = sum(X)
for i in range(N):
    if X[i] == 0:
        X[i] = 1
        print(f(X, popcount + 1))
        X[i] = 0
    else:
        X[i] = 0
        print(f(X, popcount - 1))
        X[i] = 1

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

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

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
    exit()
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Submission status: Wrong Answer

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

def popctmod(n):
  return n % bin(n).count('1')

memo = {}
for i in range(N):
  if X[i]=='1':
    bitStr = X[:i] + '0' + X[i+1:]
  else:
    bitStr = X[:i] + '1' + X[i+1:]
  num = int(bitStr, 2)
  tempnum = num
  if num in memo:
    print(memo[num])
    continue
  res = 0
  while num!=0:
    num = popctmod(num)
    res += 1
  memo[num] = res
  print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

t = [0]

pl = np.array([1])
tmp = [np.array([1])]
for i in range(18):
    ne = np.concatenate([tmp[-1], tmp[-1]+1])
    tmp.append(ne)
pl = np.concatenate(tmp)
print(pl)

for n in range(1, N+1):
    c = pl[n-1]
    t.append(1 + t[n%c])

base = X.count("1")
basex = int(X, 2)
for n in range(N):
    if X[n] == "0":
        c = base + 1
        x = basex + 2**(N-n-1)
    else:
        c = base - 1
        x = basex - 2**(N-n-1)
    
    if c == 0:
        print(0)
    elif c == 1:
        print(1)
    elif c == 2:
        print(2)
    else:
        print(1 + t[x%c])

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 0
    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 = [0]

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(0)
        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(0)
else:
    print(Ans[tmp%cur])
#print(solve(N,cnt))

Submission status: Wrong Answer

Solution code:
n = int(input())
binary = input()
binary_n = int(binary, 2)
table = [None]*(2*(10**5)+1)
for i in range(2*(10**5)+1):
    ans = 0
    ii = i
    while ii > 0:
        if table[ii] is not None:
            ans += table[ii]
            break
        ii %= bin(ii).count('1')
        ans += 1
    table[i] = ans

div = binary.count('1')
for dg in range(n-1, -1, -1):
    pc = div
    if binary[dg] == 1:
        pc -= 1
    else:
        pc += 1

    bn = binary_n ^ (1 << dg)
    if bn > 2*(10**5) + 1:
        score = table[bn%pc]+1
    else:
        score = table[bn]
    print(score)

Submission status: Wrong Answer

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

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

dp = [-1]*10**5

dp[0] = 0
dp[1] = 1

for i in range(2,10**5):
    f = 0
    k = i
    while k != 0:
        k = k % bin(k).count('1')
        f += 1
        if dp[k] != -1:
            dp[i] = f + dp[k]

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

for i in range(n):
    if x[n-i-1] == '0':
        number = num + 2**(n-i-1)
    else:
        number = num - 2**(n-i-1)
    f = 0
    while number > 10**5:
        number = number % bin(number).count('1')
        f += 1
    print(f + dp[number])

Submission status: Wrong Answer

Solution code:
class FuncMemo(dict):
    def __missing__(self, key):
        count = 0
        while key > 0:
            count += 1
            key %= popcount_memo[key]
        self[key] = count
        return count


class PopcountMemo(dict):
    def __missing__(self, key):
        value = bin(key).count('1')
        self[key] = value
        return value


popcount_memo = PopcountMemo()
func_memo = FuncMemo()


def main():
    digits = int(input())
    binary_num = '0b' + input()
    int_num = int(binary_num, 0)
    for shift in range(digits - 1, -1, -1):
        num_tmp = int_num ^ (1 << shift)
        print(func_memo[num_tmp])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
X=input()
Xint = int(X, 2)
res = [0]*N
bc = X.count('1')
if bc > 1:
    amari_2 = Xint%(bc+1)
    amari_3 = Xint%(bc-1)
    first = [0]*N
    for i in range(N):
        bc_tmp = bc
        if X[i]=='1':
            first[i] = (amari_3 - pow(2,N-i-1,bc-1))%(bc-1)
        else:
            first[i] = (amari_2 + pow(2,N-i-1,bc+1))%(bc+1)
    for i in range(N):
        c = 1
        tmp = first[i]
        if tmp==0:
            print(1)
            continue
        while 1:
            bc = bin(tmp).count('1')
            tmp = tmp%bc
            c += 1
            if tmp == 0:
                res[i] = c
                print(c)
                break
else:
    for i in range(N):
        c = 0
        tmp = Xint + pow(2,N-i-1)
        if X[i] == '1':
            tmp = Xint - pow(2,N-i-1)
        if tmp==0:
            print(1)
            continue
        while 1:
            bc = bin(tmp).count('1')
            tmp = tmp%bc
            c += 1
            if tmp == 0:
                res[i] = c
                print(c)
                break

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)
    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:
N = int(input())
X = list(input())
s = []
for i in range(0,N):
    t = 0; u = 0
    if X[i]=="0":
        X[i] = "1"
    elif X[i]=="1":
        X[i] = "0"
    a = "".join(X)
    t = int(a,2)
    while(t > 0):
        a1 = bin(t)
        a2 = str(a1)
        b1 = list(a1)
        c1 = b1.count("1")
        t = t%c1
        u += 1
    s.append(u)
for i in s:
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	X = inputStr()
	X_lin = list(X)

	ans_tmp = 0
	oct = int(X, 2)
	while True:
		if oct == 0:
			break
		tmp = bc(oct)
		oct = oct % tmp
		ans_tmp += 1

	base = ans_tmp

	ans = []
	mem = {}
	ama = {}
	for i in range(N):
		if X_lin[i] == "0":
			ans.append(base)
			continue
		oct_mae = []
		oct = 2**(N-i-1)

		oct_mae.append(oct)

		ans_tmp = 0
		if oct in mem:
			ans_tmp = mem[oct]
		else:
			while True:
				if oct == 0:
					break
				tmp = bc(oct)
				oct = oct % tmp
				ans_tmp += 1
				oct_mae.append(oct)
				if oct == 0:
					break
				if oct in mem:
					ans_tmp += mem[oct]
					break

		ans.append(ans_tmp)
		if oct_mae[0] in mem:
			pass
		else:
			for i,val in enumerate(oct_mae):
				mem[val] = ans_tmp
				ans_tmp -= 1

	for i in ans:
		print(i)
	#print(mem)

def bc(x):
	return bin(x).count("1")

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
X=list(input())
X=list(map(int,X))
#print(X)
ans1=0
ans2=0
c=collections.Counter(X)
div=c[1]
for i in range(N):
    ans1=(ans1+X[i]*pow(2,N-i-1,div+1))%(div+1)
    if div-1!=0:
        ans2=(ans2+X[i]*pow(2,N-i-1,div-1))%(div-1)
    else:
        ans2=None
    #print(ans1)
#print(ans1,div+1)
#print(ans2,div-1)
#ここまででXについてのXのbit数、X%(Xのbit数)がわかる
for i in range(N):
    cnt = 1
    if (X[i]==0):
        num=(ans1+pow(2,N-i-1,div+1))%(div+1)
        #print(num)
    else:
        if (div-1)!=0:
            num=(ans2+div-1-pow(2,N-i-1,div-1))%(div-1)
        else:
            cnt=0
            print(cnt)
            break
        #print(num)
    while num != 0:
        di = 0
        for j in range(18):
            if (num >> j)&1 == 1:
                di = di + 1
        num = num % di
        cnt = cnt + 1
    print(cnt)

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)
            ans1 %= Xc+1
            ans2 += pow(2,N-1-j,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()