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, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(x):
    # x is a 64-bit integer
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

Submission status: Wrong Answer

Solution code:
def popcount(n):
    return bin(n).count('1')


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

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit

        if pcount_Xi == 0:
            print(0)
            continue

        n = ((X_int % pcount_Xi) + (pow(2, N-i-1, pcount_Xi) * (-1)**bit)) % pcount_Xi

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)

Submission status: Wrong Answer

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

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

tmp_pop_X = X.count('1')
X_tmp = int(X,2)

for i in range(N):
    if X[i] == '0':
        X_next = X_tmp + pow(2,N-1-i,tmp_pop_X+1)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = X_tmp - pow(2,N-1-i,tmp_pop_X+1)
        X_pop_next = tmp_pop_X - 1
        
    if X_pop_next == 0:
        print(0)
        continue
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
    
    print(ans)

Submission status: Wrong Answer

Solution code:
def popcount(n):
    return bin(n).count('1')

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

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        bit = int(bit)
        pcount_Xi = pcount_X + (-1)**bit
        mask = 1 << (N-i-1)
        n = X_int + (mask * (-1)**bit)

        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
N = int(input())
S = input()

c = S.count('1')
m = int('0B'+S, 0)
memo = [0]*(N+1)

@lru_cache(maxsize=None)
def calc(a):
    global ans
    if a == 0: return ans
    ans += 1
    if a <= N:
        if memo[a] != 0:
            m = memo[a]
        else:
            m = bin(a).count('1')
            memo[a] = m
    else: m = bin(a).count('1')
    return calc(a%m)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)
    
    ans = 0
    print(calc(a))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
N = int(input())
S = input()

c = S.count('1')
m = int('0B'+S, 0)

@lru_cache(maxsize=None)
def calc(a):
    global ans
    if a == 0: return ans
    ans += 1
    m = bin(a).count('1')
    return calc(a%m)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)
    
    ans = 0
    print(calc(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = input()
n = sum([(2 ** i) * int(x) for i,x in enumerate(reversed(X))])

from functools import lru_cache

@lru_cache(maxsize=None)
def popcount(x):
    return bin(x)[2:].count('1')
    
@lru_cache(maxsize=None)
def f(x):
    cnt = 1
    if x == 0:
        return cnt
    
    while x%popcount(x):
        cnt += 1
        x %= popcount(x)
    return cnt

for i in reversed(range(N)):
    x = n ^ (1<<i)
    print(f(x))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

x=int(xs,2)

nmax=2*10**5
xmem=[0]*(nmax+1)
for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xs[n-1-i]=="0":
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                if xi<nmax and xmem[xi]>0:
                    icnt=xmem[xi]
                    break
                icnt+=1
                xmem[xi]=icnt
                xi=xi%(bin(xi).count("1"))
            print(icnt)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

def popcount2(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

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

def popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp2 = tmp % popcount(tmp)
        while tmp2 > 0:
            tmp %= popcount(tmp)
            cnt += 1
            tmp2 %= popcount(tmp2)
        print(cnt)
    except:
        print(0)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)

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

nbits=sum([int(X[i]) for i in range(N)])


# print(nbits)

MAXBIT=60
def strmod(bitstr,m):
    # print(bitstr, " m=", m)
    if m <= 0:
        return "0"

    if len(bitstr)>MAXBIT:
        l = eval("0b"+bitstr[:MAXBIT])
        l_bitstr="{:b}".format(l % m)
        ans=strmod(l_bitstr+bitstr[MAXBIT:], m)
    else:
        ans="{:b}".format(eval("0b"+bitstr) % m)
    return ans

precalc_str_plus = strmod(X,nbits+1)
precalc_str_minus = strmod(X,nbits-1)

precalc_plus = eval('0b'+precalc_str_plus)
precalc_minus = eval('0b'+precalc_str_minus)

print(precalc_plus, precalc_minus)

for i in range(N):



    Y='1'+'0'*(N-i-1)
    modY_str_plus = strmod(Y,nbits+1)
    modY_str_minus = strmod(Y,nbits-1)

    modY_plus = eval('0b'+modY_str_plus)
    modY_minus = eval('0b'+modY_str_minus)

    # print("i=",i, "Y='",Y,"' ", precalc_plus, modY_plus, precalc_minus, modY_minus)

    if X[i]=='0':
        m = (precalc_plus + modY_plus) % (nbits+1)
        ans = 1
    else:
        if nbits == 1:
            m=0
            ans = 0
        else:
            m = (nbits-1 + precalc_minus - modY_minus) % (nbits-1)
            ans = 1

    while m > 0:
        # print(ans, "m=", m)
        ans += 1
        mstr = "{:b}".format(m)
        m = m % sum([int(mstr[i]) for i in range(len(mstr))])

    print(ans)

Submission status: Wrong Answer

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i+1,mod))%(mod)

        print(1+f(amari))


main()

Submission status: Wrong Answer

Solution code:
#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == 1) and X10_num1 >1:
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)
        elif (X[j] == 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()

Submission status: Wrong Answer

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

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

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

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

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

    return cnt

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


for i in range(N,0,-1):
    a = X10
    if (a>>(i-1) & 1) and X10_num1 >1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

    elif (a>>(i-1) & 1) and X10_num1 ==0:
        print(0)
        continue
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari 
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)

Submission status: Wrong Answer

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

cnt=x.count("1")
p_cnt=cnt+1
m_cnt=cnt-1
p_amari,m_amari=0,0

p_amari=val%(cnt+1)
if cnt-1!=0:
  m_amari=val%(cnt-1)
else:
  m_amari=0

for i in range(n):
  ans=0
  if x[i]=="0":
    amari=p_amari+pow(2,n-i-1,p_cnt)
    amari%p_cnt
  elif x[i]=="1":
    if cnt-1==0:
      print(0)
      continue
    amari=m_amari-pow(2,n-i-1,m_cnt)
    amari%=m_cnt
  ans+=1
  while amari!=0:
    amari%=bin(amari).count("1")
    ans+=1
  print(ans)

Submission status: Wrong Answer

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

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in  reversed(range(N)):
            if X[i] == '1':
                print(0) #全てが0になる
            else:
                if i==N-1:
                    print((int(X[N-1])+1)%2+1) # 2の剰余の反転
                else:
                    print((int(X[N-1]))%2+1) # 2の剰余
        return

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


    CHA = list(set(TEMP))

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in  reversed(range(N)):
            if X[i] == '1':
                print(0) #全てが0になる
            else:
                if i==N-1:
                    print((int(X[N-1])+1)%2) # 2の剰余の反転
                else:
                    print(int(X[N-1])) # 2の剰余
        return

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


    CHA = list(set(TEMP))

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in  reversed(range(N)):
            if X[i] == '1':
                print(0) #全てが0になる
            else:
                if i==N-1:
                    print((int(X[N-1])+1)%2) # 2の剰余の反転
                else:
                    print(int(X[N-1])) # 2の剰余
        return

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


    CHA = list(set(TEMP))

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in range(N):
            if X[N-i-1] == '1':
                print(0) #全てが0になる
            else:
                if i==0:
                    print((int(X[N-1])+1)%2) # 2の剰余の反転
                else:
                    print(int(X[N-1])) # 2の剰余
        return

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


    CHA = list(set(TEMP))

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

    m = 0
    pmod = 1
    mmod = 1
    p = XINT % (cnt+1)
    if cnt != 1:
        m = XINT % (cnt-1)
    for i in range(N):
        ANS[i] = 1
        if (X[N-i-1] == '0'):
            TEMP[i] = (p + pmod) % (cnt+1)
        else:
            if cnt == 1:
                if X[N-i-1] == '1':
                    TEMP[i] = 0 #全てが0になる
                else:
                    if i==0:
                        TEMP[i] = (int(X[N-1])+1)%2 # 2の剰余の反転
                    else:
                        TEMP[i] = int(X[N-1]) # 2の剰余
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        if cnt != 1:
            mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

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

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




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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

    m = 0
    pmod = 1
    mmod = 1
    p = XINT % (cnt+1)
    if cnt != 1:
        m = XINT % (cnt-1)
    for i in range(N):
        ANS[i] = 1
        if (X[N-i-1] == '0'):
            TEMP[i] = (p + pmod) % (cnt+1)
        else:
            if cnt == 1:
                if X[N-i-1] == '1':
                    TEMP[i] = 0 #全てが0になる
                else:
                    TEMP[i] = int(X[N-1]) # 2の剰余
            else:
                TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        if cnt != 1:
            mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

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

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




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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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


    CHA = list(set(TEMP))

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

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




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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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

    m = 0
    pmod = 1
    mmod = 1
    p = XINT % (cnt+1)
    if cnt == 1:
        mmod=0
    else:
        m = XINT % (cnt-1)

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


    CHA = list(set(TEMP))

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

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




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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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


    CHA = list(set(TEMP))

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

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




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

if __name__ == '__main__':
    main()