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=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()
if px==1:
    for i in range(n):
        if int(x_[-i-1]):
            print(0)
        else:
            if not i:
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    
    cnt=1
    while tmp:
        if not dv:
            break
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()
if px==1:
    for i in range(n):
        if int(x_[-i-1]):
            print(0)
        else:
            if not i:
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        if not dv:
            break
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
X2 = [int(i) for i in X]
S = int(X, 2)

p = bin(S).count("1")
a = S % (p + 1)
b = S % (p - 1) if p - 1 else 0

def f(n):
    r = 1
    while n:
        n = n % bin(n).count("1")
        r += 1
    return r

d = 2 ** N
for i in range(1, N+1):
    d = d // 2
    if not X2[i-1]:
        if S + d == 0:
            print(0)
            continue
        t = a + d
        s = t % (p + 1)
    else:
        if b == 0 or S - d == 0:
            print(0)
            continue
        t = b - d
        s = t % (p - 1)
    print(f(s))

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    k0 = 0
    k1 = 0
    # if d > 0:
    #     k0 = k % (d-1)
    # k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        cnt = 0
        if x[i] == '1' and d - 1 > 0:
            cnt += f[(k0 - pow(2, n - i - 1, d - 1)) % (d - 1)] + 1
        elif x[i] == '0':
            cnt += f[(k1 + pow(2, n - i - 1, d + 1)) % (d + 1)] + 1
        wi(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = X.count('1')
if cnt == 1:
    for x in X:
        if x == '0':
            print(1)
        else:
            print(0)
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    # k = int(x, 2)
    d = x.count('1')
    k0 = 0
    k1 = 0
    # if d > 0:
    #     k0 = k % (d-1)
    # k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        cnt = 0
        if x[i] == '1' and d - 1 > 0:
            cnt += f[(k0 - pow(2, n - i - 1, d - 1)) % (d - 1)] + 1
        elif x[i] == '0':
            cnt += f[(k1 + pow(2, n - i - 1, d + 1)) % (d + 1)] + 1
        wi(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = X.count('1')
if cnt == 1:
    print(*([1] * N), sep='\n')
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
N = int(input())
X = int(str(input()), 2)
X_bin = format(X, '0'+str(N)+'b')

ans = [0] * N
dp = [0] * 2 ** (20 + 1)
for i in range(N):
    if X_bin[i] == '1':
        n = X - (1 << (N - 1 - i))
    else:
        n = X + (1 << (N - 1 - i))

    tmp = []
    while n != 0:
        try:
            n < 2 ** (20 + 1)
            if dp[n]:
                ans[i] += dp[n]
                break
            tmp.append(n)
            n = n % format(n, '0' + str(N) + 'b').count('1')
            ans[i] += 1
            for j in range(len(tmp)):
                dp[tmp[j]] = ans[i] - j
        except IndexError:
            n = n % format(n, '0'+str(N)+'b').count('1')
            ans[i] += 1

    print(ans[i])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

#bi = 1 << N
for i in range(N):
    #bi = bi >> 1
    if X[i] == '0':
        #res = (plu + bi % (pop+1)) % (pop+1)
        res = (plu + pow(2, N-1-i, pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        #res = (mai - bi % (pop-1)) % (pop-1)
        res = (mai + pow(2, N-1-i, pop-1)) % (pop-1)
    print(arr[res] + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = list(map(int, list(input())))
one = Counter(X)[1]


if one > 1:
    Sm = 0
    mm = one - 1
    tm = 1
    for i in range(N - 1, -1, -1):
        tm %= mm
        if X[i] == 1:
            Sm += tm
            Sm %= mm
        tm *= 2

Sp = 0
mp = one + 1
tp = 1
for i in range(N - 1, -1, -1):
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sp %= mp
    tp *= 2


memo = [-1] * (2 * (10 ** 5) + 10)
memo[0] = 0

for i in range(N):
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    elif one > 1:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    else:
        print(0)
        continue
    print(dfs(m))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1 and x[-1]=="1":
    for i in range(n-1):
        print(2)
    print(0)
    exit()

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#from maru65536

n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=n-x.index('1')-1
    for i in range(n):
        if i==z:
            print(0)
        else:
            print(1)
    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i]+p-1)%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
if x.count("1")==0:
  for i in x:
    print(1)
else:
  print(-10)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
if x.count("1")==0:
  for i in x:
    print(1)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = [int(x) for x in input()]
debug('n {}'.format(n))
# debug('X {}'.format(X))
debug('X {}'.format(''.join(map(str,X))))
po = sum(X)
debug('po {}'.format(po))
debug('===')

M = []
for i in range(n):
    pi  = po + (-1 if X[i] else 1)
    X[i] = 0 if X[i] else 1
    debug('pi {}'.format(pi))
    # debug('X {}'.format(X))
    debug('X {}'.format(''.join(map(str,X))))

    r = 0
    for x in X:
        r = (r<<1) + x
        if r >= pi: r -= pi
    debug('r {}'.format(r))
    M.append([x,r])
    X[i] = 0 if X[i] else 1

debug('M {}'.format(M))
debug('===')

for m in M:
    x,r = m
    debug('x {} r {}'.format(x,r))
    c = 1
    ni = r
    while ni > 0:
        pi = 0
        xi = []
        while ni > 0:
            b = ni & 1
            pi += b
            xi.append(b)
            ni >>= 1
        # debug('xi {}'.format(xi))
        # xi.reverse()
        debug('pi {}'.format(pi))
        debug('xi {}'.format(xi))
        r = 0
        for b in xi[::-1]:
            r = (r<<1) + b
            if r >= pi: r -= pi
        debug('r {}'.format(r))
        debug('---')
        c += 1
        ni = r

    # debug('c {}'.format(c))
    # debug('---')
    print(c)
    X[i] = 0 if X[i] else 1
debug('===')

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=n-x.index('1')-1
    for i in range(n):
        if i==z:
            print(0)
        else:
            print(1)
    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = [int(x) for x in input()]
debug('n {}'.format(n))
# debug('X {}'.format(X))
debug('X {}'.format(''.join(map(str,X))))
po = sum(X)
debug('po {}'.format(po))
debug('===')

for i in range(n):
    pi  = po + (-1 if X[i] else 1)
    X[i] = 0 if X[i] else 1
    debug('pi {}'.format(pi))
    # debug('X {}'.format(X))
    debug('X {}'.format(''.join(map(str,X))))

    r = 0
    for b in X:
        r = (r<<1) + b
        if r >= pi: r -= pi
    debug('r {}'.format(r))
    debug('---')

    c = 1
    ni = r
    while ni > 0:
        pi = 0
        xi = []
        while ni > 0:
            b = ni & 1
            pi += b
            xi.append(b)
            ni >>= 1
        debug('xi {}'.format(xi))
        xi.reverse()
        debug('pi {}'.format(pi))
        debug('xi {}'.format(xi))
        r = 0
        for b in xi:
            r = (r<<1) + b
            if r >= pi: r -= pi
        debug('r {}'.format(r))
        debug('---')
        c += 1
        ni = r

    # debug('c {}'.format(c))
    # debug('---')
    print(c)
    X[i] = 0 if X[i] else 1
debug('===')

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
p=x.count('1')

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    for i in range(n):
        if i==z:
            print(0)
        else:
            print(1)
    exit()

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count

#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp)+1)

Submission status: Wrong Answer

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

Submission status: 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)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    a=x10%(cnt+1)
    if cnt==1:
        b=0
    else:
        b=x10%(cnt-1)
    for i in range(n):
        if x[i]=='1' and cnt==1:
            print(0)
            continue
        elif x[i]=='1':
            cal=b-pow(2,n-1-i,cnt-1)
        else:
            cal=a+pow(2,n-1-i,cnt+1)
        print(f(cal)+1)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = [int(x) for x in input()]
debug('n {}'.format(n))
# debug('X {}'.format(X))
debug('X {}'.format(''.join(map(str,X))))
po = sum(X)
debug('po {}'.format(po))
debug('===')

for i in range(n):
    # xi = 0 if X[i] else 1
    # debug('i {} n-i-1 {} xi {}'.format(i,n-i-1, xi))
    pi  = po + (-1 if X[i] else 1)
    X[i] = 0 if X[i] else 1
    debug('pi {}'.format(pi))
    # debug('X {}'.format(X))
    debug('X {}'.format(''.join(map(str,X))))

    r = 0
    for b in X:
        r = (r<<1) + b
        if r >= pi: r -= pi
    debug('r {}'.format(r))
    debug('---')

    c = 1
    ni = r
    while ni > 0:
        xi = format(ni, 'b')
        pi = xi.count('1')
        debug('pi {}'.format(pi))
        debug('xi {}'.format(xi))
        r = 0
        for b in xi:
            debug('b {}'.format(b))
            r = (r<<1) + int(b)
            if r >= pi: r -= pi
        debug('r {}'.format(r))
        debug('---')
        c += 1
        ni = r

    debug('c {}'.format(c))
    debug('---')
    print(c)
    X[i] = 0 if X[i] else 1
debug('===')

Submission status: Wrong Answer

Solution code:
n=int(input())
x=input()
p=0
chk0=chk1=chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0

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

Submission status: 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)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    if cnt==1:
        e=x10%2
        for i in range(n):
            if x[i]=='1':
                print(f(e-pow(2,n-1-i,2))+1)
            else:
                print(f((e+pow(2,n-1-i,2))+1))
    if cnt==0:
        for i in range(n):
            print(1)
    if cnt>1:
        a,b=x10%(cnt-1),x10%(cnt+1)
        for i in range(n):
            if x[i]=='1':
                print(f(a-pow(2,n-1-i,cnt-1))+1)
            else:
                print(f(b+pow(2,n-1-i,cnt+1))+1)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def pop_count(n):
    return sum(n >> i & 1 for i in range(n.bit_length()))


def f(n):
    if n == 0:
        return 0
    return f(n % pop_count(n)) + 1


N = int(input())
X = input()
p = X.count("1")
rem_plus = 0
rem_minus = 0
for i in range(N):
    k = N - i - 1
    if X[i] == "0":
        continue
    elif p > 1:
        rem_minus = (rem_minus + pow(2, k, p - 1)) % (p - 1)
    rem_plus = (rem_plus + pow(2, k, p + 1)) % (p + 1)
for i in range(N):
    k = N - i - 1
    if X[i] == "0":
        print(f((rem_plus + pow(2, k, p + 1)) % (p + 1)) + 1)
    elif p > 1:
        print(f((rem_minus - pow(2, k, p - 1)) % (p - 1)) + 1)
    else:
        print("jdsksfa", 0)

Submission status: Wrong Answer

Solution code:
#!python3

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


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


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


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

source_one = X.count('1')

import collections

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

source_n = int(X, 2)

kijou = 2 ** N

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

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

    n = original_n % one_count



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

Submission status: Wrong Answer

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

one_num = X.count("1")

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

Submission status: Wrong Answer

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

one_num = X.count("1")

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

Submission status: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
c = X.count('1')
if c == 0:
  for i in range(N):
    print(1)
  quit()
if c == 1:
  if int(X[-1]):
    for i in range(N-1):
      print(2)
    print(0)
  else:
    for i in range(N):
      if int(X[i]):
        print(0)
      else:
        print(1)
  quit()

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res

for i in range(3, 2*10**5+1):
  calc(i)

Xmodp = Xmodm = 0
digit_p = digit_m = 1
digit = {}
for i in range(N):
  if int(X[-i-1]):
    Xmodp += digit_p
    Xmodp %= c + 1
    Xmodm += digit_m
    Xmodm %= c - 1
  digit[i] = [digit_p, digit_m]
  digit_p = (digit_p * 2) % (c+1)
  digit_m = (digit_m * 2) % (c-1)

ans = []
for i in range(N):
  x = int(X[-i-1])
  if x:
    ans.append(memo[(Xmodm - digit[i][1]) % (c-1)] + 1)
  else:
    ans.append(memo[(Xmodp + digit[i][0]) % (c+1)] + 1)

ans = ans[::-1]
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
c = X.count('1')
if c == 0:
  for i in range(N):
    print(1)
  quit()
if c == 1:
  if X[-1] == 1:
    for i in range(N-1):
      print(2)
    print(0)
  else:
    for i in range(N):
      if int(X[i]):
        print(0)
      else:
        print(1)
  quit()

memo = {0:0, 1:1, 2:1}
def calc(x):
  global memo
  if x in memo:
    return memo[x]
  c = bin(x).count('1')
  y = x % c
  res = calc(y) + 1
  memo[x] = res

for i in range(3, 2*10**5+1):
  calc(i)

Xmodp = Xmodm = 0
digit_p = digit_m = 1
digit = {}
for i in range(N):
  if int(X[-i-1]):
    Xmodp += digit_p
    Xmodp %= c + 1
    Xmodm += digit_m
    Xmodm %= c - 1
  digit[i] = [digit_p, digit_m]
  digit_p = (digit_p * 2) % (c+1)
  digit_m = (digit_m * 2) % (c-1)

ans = []
for i in range(N):
  x = int(X[-i-1])
  if x:
    ans.append(memo[(Xmodm - digit[i][1]) % (c-1)] + 1)
  else:
    ans.append(memo[(Xmodp + digit[i][0]) % (c+1)] + 1)

ans = ans[::-1]
print(*ans, sep='\n')