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()

binans=int(x,2)
  
bincount=x.count('1')

def popcount(s):
  cnt=0
  while s!=0:
    if s%2==1:
      cnt+=1
    s//=2
  
  return cnt

def f(s):
  ans=0
  if s==0:
    return 0
  if s==1:
    return 1

  dict=[popcount(bincount+1),popcount(bincount-1)]

  if bin(s).count('1')==bincount+1:
    ans+=1
    s=s%dict[0]
  elif bin(s).count('1')==bincount-1:
    ans+=1
    s=s%dict[1]

  while s!=0:
    ans+=1
    s=s%popcount(s)
    
  return ans

for i in range(n):
  if x[i]=='0':
    xxx=binans+2**(n-i-1)
    bincount+=1
    
  else:
    xxx=binans-2**(n-i-1)
    bincount-=1
  
  print(f(xxx))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')


if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if X[i] == '0':
                print(1)
            else:
                print(0)
        exit()

mod_plus_1, mod_minus_1 = 0, 0
for i in range(N):
    mod_plus_1 = (mod_plus_1*2+int(X[i])) % (pc+1)
    mod_minus_1 = (mod_minus_1*2+int(X[i])) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1 - 2**(N-1-i) % (pc-1)
        x %= (pc-1)

    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')

if pc == 0 or pc == 1:
    print(0)
    exit()

mod_plus_1 = int(X, 2) % (pc+1)
mod_minus_1 = int(X, 2) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1 + 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1 - 2**(N-1-i) % (pc-1)
        x %= (pc-1)
    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')

if pc == 0 or pc == 1:
    print(0)
    exit()

mod_plus_1 = int(X, 2) % (pc+1)
mod_minus_1 = int(X, 2) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1
        x += 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1
        x -= 2**(N-1-i) % (pc-1)
        x %= (pc+1)
    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = input()
pc = X.count('1')

if pc == 0:
    print(*[1]*N, sep='\n')
    exit()
elif pc == 1:
    if int(X, 2) == 1:
        for i in range(N-1):
            print(2)
        print(0)
        exit()
    else:
        for i in range(N):
            if X[i] == '0':
                print(1)
            else:
                print(0)
        exit()


mod_plus_1 = int(X, 2) % (pc+1)
mod_minus_1 = int(X, 2) % (pc-1)


def f(x):
    if x == 0:
        return 0
    else:
        return f(x % bin(x).count('1'))+1


for i in range(N):
    if X[i] == '0':
        x = mod_plus_1
        x += 2**(N-1-i) % (pc+1)
        x %= (pc+1)
    else:
        x = mod_minus_1
        x -= 2**(N-1-i) % (pc-1)
        x %= (pc+1)
    if x == 0:
        print(1)
    else:
        print(f(x)+1)

Submission status: Wrong Answer

Solution code:
import copy
 
# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
# 元の二進数に含まれる1の個数を算出
org_num_1 = bit_num.count('1')
# 二進数の各ビットを反転した二進数を格納する配列を初期化
xor_list = []
# 各ビットを反転した二進数を作成
for i in range(digit_n):
    xor_list = copy.copy(bit_num)
    bit_i = 1^int(bit_num[i])
    xor_list[i] = str(bit_i)
    # 割る数を二進数に出現する1の数で初期化
    div_num_1 = org_num_1 + (-1)**(1 + bit_i)
    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    # 割る数を二進数表記の文字列に変換
    sam_num = ''.join(xor_list)
    #剰余を格納する変数に反転した二進数を文字列から数値に変換した値をセットして初期化
    surplus = int(sam_num)
    # 操作回数を格納する変数に0をセットして初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div_num_1
        div_num_1 = str(bin(surplus)).count('1')
        print(div_num_1)
        #div_num_1 = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Wrong Answer

Solution code:
def g(x):
  S=format(x,"40b")
  cnt=0
  for i in range(35):
    if S[-1-i]=="1":
      cnt=cnt+1
  return x%cnt

n=int(input())
X=input()
a=0
for i in range(n):
  if X[i]=="1":
    a=a+1
#最初に割るのは a-1 or a+1 -> a==0,1 に注意
if a==0:
  for i in range(n):
    print(1)
  exit()
if a==1:
  if X[-1]=="1":
    for i in range(n-1):
      print(2)
    print(0)
    exit()
  else:
    for i in range(n):
      if X[i]=="1":
        print(0)
      else:
        print(1)
    exit()
D=[0]*n
E=[0]*n
D[0]=1%(a-1)
E[0]=1%(a+1)
b=int(X[-1])%(a-1)
c=int(X[-1])%(a+1)
for i in range(n-1):
  D[i+1]=(D[i]*2)%(a-1)
  E[i+1]=(E[i]*2)%(a+1)
  if X[-2-i]=="1":
    b=(b+D[i+1])%(a-1)
    c=(c+E[i+1])%(a+1)
for i in range(n):
  if X[i]=="1":
    x=(b+a-1-D[-1-i])%(a-1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)
  else:
    x=(c+E[-1-i])%(a+1)
    ans=1
    while x!=0:
      x=g(x)
      ans=ans+1
    print(ans)

Submission status: Wrong Answer

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

def main():
  n = int(input())
  x = input()
  count = 0
  sub = 1
  last = [None]*n
  for i in range(n):
    if x[i] == "1":
      count += 1
            
  if count == 0:
    for i in range(n):
      print(0)
    sys.exit()
  if count == 1:
    if x[-1] == "1":
      for i in range(n-1):
        print(2)
      print(0)
      sys.exit()
    else:
      for i in range(n-1):
        if x[i] == "1":
          print(0)
        else:
          print(1)
      print(2)
      sys.exit()

  sub1, sub2 = 1, 1
  num1, num2 = 0, 0
  for i in range(n):
    if count-1 == 1:
      sub1 = 0
    last[i] = [sub1, sub2]
    if x[n-i-1] == "1":
      num1 += sub1
      num2 += sub2
      num1 %= count-1
      num2 %= count+1
    sub1 *= 2
    sub2 *= 2
    sub1 %= count-1
    sub2 %= count+1
            
    
    
  key = [0]*(2**18+1)
  for i in range(1, 2**18):
    c = 0
    for j in range(18):
      if (i>>j)&1:
        c += 1
    judge = i%c
    key[i] = key[judge] + 1

  for i in range(n):
    if x[i] == "1":
      judge = (num1+count-1-last[n-1-i][0])%(count-1)
      print(1+key[judge])
    else:
      judge = (num2+last[n-1-i][1])%(count+1)
      print(1+key[judge])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = input()

    cnt_init = X.count("1")
    x = int(X, 2)
    for i in range(n):
        if X[i] == "0":
            cnt = cnt_init + 1
            x = (x + pow(2, (n - i - 1), cnt)) % cnt
            res = 1
        else:
            cnt = cnt_init - 1
            if cnt != 0:
                x = (x - pow(2, (n - i - 1), cnt)) % cnt
                res = 1
            else:
                x = 0
                res = 0

        while x:
            cnt = bin(x).count("1")
            x %= cnt
            res += 1
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
X = input()
n = int(X,2)
p=defaultdict(int)
for i in range(N):
    a = list(X)
    if(a[i] == '0'):
        a[i] = '1'
        x =  a.count('1')
        while(n!=0):
            t = n%(x+1)
            n = t
            p[i]+=1
    else:
        a[i] = '0'
        x =  a.count('1')
        while(n!=0):
            t = n%(x+1)
            n = t
            p[i]+=1
for i in range(N):
    print(p[i])

Submission status: Wrong Answer

Solution code:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
# 元の二進数に含まれる1の個数を算出
div_num_1 = bit_num.count('1')
# 各ビットを反転した二進数を作成
# 各ビットを反転した二進数を格納する配列を初期化
xor_list = ['1'] * digit_n
for i in range(digit_n):
    # 二進数の各ビットを反転した二進数を配列に格納
    for j in range(len(bit_num)):
        if j == i:
            bit_i = int(xor_list[j])^int(bit_num[j])
            xor_list[j] = str(bit_i)
            # 反転した二進数に含まれる1の個数を算出(1なら1増え、0なら1減る)
            div_num_1 = div_num_1 + (-1)**(1+bit_i)
        else:
            xor_list[j] = copy.copy(bit_num[j])

    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    #剰余を格納する変数に反転した二進数をセットして初期化
    surplus = int(str("0b"+''.join(xor_list)),0)
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div_num_1
        div_num_1 = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Wrong Answer

Solution code:
import copy

# 二進数のビット数
digit_n = int(input())
# 二進数
bit_num = list(input())
# 元の二進数に含まれる1の個数を算出
div_num_1 = bit_num.count('1')
# 各ビットを反転した二進数を作成
# 各ビットを反転した二進数を格納する配列を初期化
xor_list = ['1'] * digit_n
for i in range(digit_n):
    # 二進数の各ビットを反転した二進数を配列に格納
    for j in range(len(bit_num)):
        if j == i:
            bit_i = int(xor_list[j])^int(bit_num[j])
            xor_list[j] = str(bit_i)
            # 反転した二進数に含まれる1の個数を算出(1なら1増え、0なら1減る)
            div_num_1 = div_num_1 + (-1)**(1+bit_i)
        else:
            xor_list[j] = copy.copy(bit_num[j])

    # 各ビットを反転した二進数を二進数に含まれている1の個数で割った剰余に置き換えて、剰余が0になるまでの操作回数を出力
    sam_num = "0b"+''.join(xor_list)
    #剰余を格納する変数に反転した二進数を10進数に変換した数値をセットして初期化
    surplus = int(sam_num, 0)
    # 操作回数を格納する変数を0で初期化
    l_count = 0
    while(surplus != 0):
        l_count += 1
        surplus = surplus % div_num_1
        div_num_1 = str(bin(surplus)).count('1')
    print(l_count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
x = input()
cnt = x.count("1")
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

xx = int(x, 2)
Y = xx % (cnt + 1)
Z = xx % (cnt - 1)

for i in range(n):
    if x[i] == '1':
        print(1 + f((Z - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)))
    else:
        print(1 + f((Y + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
x = input()
cnt = x.count("1")
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

xx = int(x, 2)
rem2 = xx % (cnt - 1)
rem1 = xx % (cnt + 1)
for j in range(n):
    if x[j] == "1":
        print(1 + f((rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)))
    else:
        print(1 + f((rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
xx = int(x, 2)
cnt = x.count("1")
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

xx = int(x, 2)
rem2 = xx % (cnt - 1)
rem1 = xx % (cnt + 1)
for j in range(n):
    if x[j] == "1":
        print(1 + f((rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)))
    else:
        print(1 + f((rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
xx = int(x, 2)
cnt = x.count("1")
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        elif i == n - 1:
            print(2)
        else:
            print(1)
    exit()

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

xx = int(x, 2)
rem2 = xx % (cnt - 1)
rem1 = xx % (cnt + 1)
for j in range(n):
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        print(1 + f(r))
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        print(1 + f(r))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
cnt = sum([int(i) for i in x])
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        else:
            if i == n - 1:
                print(2)
            else:
                print(1)
    exit()

def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))

xx = int(x, 2)
rem2 = xx % (cnt - 1)
rem1 = xx % (cnt + 1)
for j in range(n):
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        print(1 + f(r))
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        print(1 + f(r))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
cnt = sum([int(i) for i in x])
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        else:
            if i == n - 1:
                print(2)
            else:
                print(1)
    exit()

xx = int(x, 2)
rem2 = xx % (cnt - 1)
rem1 = xx % (cnt + 1)
for j in range(n):
    ans = 1
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
cnt = sum([int(i) for i in x])
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        else:
            if i == n - 1:
                print(2)
            else:
                print(1)
    exit()

ret1 = 1
ret2 = 1
rem1 = 0
rem2 = 0
for i in range(n - 1, -1, -1):
    if x[i] == "1":
        rem1 = (rem1 + ret1) % (cnt + 1)
        rem2 = (rem2 + ret2) % (cnt - 1)
    ret1 = ret1 * 2 % (cnt + 1)
    ret2 = ret2 * 2 % (cnt - 1)

for j in range(n):
    ans = 1
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


n = I()
x = S()
cnt = sum([int(i) for i in x])
if cnt == 1:
    for i in range(n - 1, -1, -1):
        if x[i] == "1":
            print(0)
        else:
            if i == n - 1:
                print(1)
            else:
                print(0)
    exit()




ret1 = 1
ret2 = 1
rem1 = 0
rem2 = 0
for i in range(n - 1, -1, -1):
    if x[i] == "1":
        rem1 = (rem1 + ret1) % (cnt + 1)
        rem2 = (rem2 + ret2) % (cnt - 1)
    ret1 = ret1 * 2 % (cnt + 1)
    ret2 = ret2 * 2 % (cnt - 1)

for j in range(n):
    ans = 1
    if x[j] == "1":
        r = (rem2 - pow(2, n - 1 - j, cnt - 1)) % (cnt - 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)
    else:
        r = (rem1 + pow(2, n - 1 - j, cnt + 1)) % (cnt + 1)
        while r:
            r = r % popcount(r)
            ans += 1
        print(ans)

Submission status: Wrong Answer

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
#X_cnt = X_bin.count('1')
for i in range(N):
    print(1)
    '''
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))
    '''

Submission status: Wrong Answer

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

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
X_cnt = X_bin.count('1')
for i in range(N):
    print(1)
    '''
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))
    '''

Submission status: Wrong Answer

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


#X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    '''
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))
    '''
    print(1)

Submission status: Wrong Answer

Solution code:
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    '''
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))
    '''
    print(1)