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:
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=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    number=num
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        number %=cnt-1
        A.append((number-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        number %=cnt+1
        A.append((number+pow(2,n-i-1,cnt+1))%(cnt+1))

for i in A:
    ans=i
    if ans==-1:print(0)
    else:
        point=1
        while ans!=0:
            ans %=popcount(ans)
            point +=1
        print(point)

Submission status: Wrong Answer

Solution code:
N = int(input())
bin_X = input()
int_X = int(bin_X, 2)

pop_cnt_1 = 0
for i in bin_X:
    if i == '1':
        pop_cnt_1 += 1
if pop_cnt_1 == 0 or pop_cnt_1 == 1:
    print(0)
    exit()
    
pop_cnt_0 = pop_cnt_1 + 1
pop_cnt_1 = pop_cnt_1 - 1

int_X_0 = int_X % pop_cnt_0
int_X_1 = int_X % pop_cnt_1

def pop_cnt(n):
    c = 0
    for i in bin(n):
        if i == '1':
            c += 1
    return c

for i in range(N):
    if bin_X == '0':
        print(0)
        continue
    
    z = 2 ** (N-i-1)
    if bin_X[i] == '1':
        n = (int_X-z)%pop_cnt_1
    else:
        n = (int_X+z)%pop_cnt_0
   
    cnt = 1
    while n != 0:
        n = n % pop_cnt(n)
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
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=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    number=num
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        number %=cnt-1
        A.append((number-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        number %=cnt+1
        A.append((number+pow(2,n-i-1,cnt+1))%(cnt+1))

B=[]
for i in A:
    ans=i
    if ans==-1:B.append(0)
    else:
        point=1
        while ans!=0:
            ans %=popcount(ans)
            point +=1
        B.append(point)

for i in B:
    print(i)

Submission status: Wrong Answer

Solution code:
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=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    number=num
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        number %=cnt-1
        A.append((number-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        number %=cnt+1
        A.append((number+pow(2,n-i-1,cnt+1))%(cnt+1))

B=[]
for i in A:
    if i==-1:B.append(0)
    else:
        point=1
        while i!=0:
            i %=popcount(i)
            point +=1
        B.append(point)

for i in B:
    print(i)

Submission status: Wrong Answer

Solution code:
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=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":
        num %=cnt-1
        A.append((num-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:
        num %=cnt+1
        A.append((num+pow(2,n-i-1,cnt+1))%(cnt+1))

B=[]
for i in A:
    if i==-1:B.append(0)
    else:
        point=1
        while i!=0:
            i %=popcount(i)
            point +=1
        B.append(point)

for i in B:
    print(i)

Submission status: Wrong Answer

Solution code:
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=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":A.append((num-pow(2,n-i-1,cnt-1))%(cnt-1))
    else:A.append((num+pow(2,n-i-1,cnt+1))%(cnt+1))

B=[]
for i in A:
    if i==-1:B.append(0)
    else:
        point=1
        while i!=0:
            i %=popcount(i)
            point +=1
        B.append(point)

for i in B:
    print(i)

Submission status: Wrong Answer

Solution code:
def popcount(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


n=int(input())
x=input()
num=int(x,2)
cnt=popcount(num)

A=[]
for i in range(n):
    if x[i]=="1" and cnt==1:A.append(-1)
    elif x[i]=="1":A.append((num-2**(n-i-1))%(cnt-1))
    else:A.append((num+2**(n-i-1))%(cnt+1))

B=[]
for i in A:
    if i==-1:B.append(0)
    else:
        point=1
        while i!=0:
            i %=popcount(i)
            point +=1
        B.append(point)

for i in B:print(i)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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


def mod(n, cnt):
    if n == 0:
        return cnt
    n = n % popcnt(n)
    cnt += 1
    return mod(n, cnt)


n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c - 1 != 0 else 0

for i in range(n):
    if x2[i] == '0':
        t = (mod1 + pow(2, n - i - 1, c + 1)) % (c + 1)
    else:
        if c - 1 != 0:
            t = (mod2 - pow(2, n - i - 1, c - 1)) % (c - 1)
        else:
            t = 0
    print(mod(t, 1))

Submission status: Wrong Answer

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = pow_2 - X_int_m
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      # pow_2 = 2**(N-i-1)%(base_1_count-1)
      # if X_int_m < pow_2:
      #   Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      # else:
      #   Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

  # if N == 1:
  #   if X.count("1"):
  #     print(1)
  #   else:
  #     print(0)
  #   return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

count = x.count("1")

mod1 = 0 # 1少ない
mod2 = 0 # 1多い

#　初回の各桁のbitを反転させた場合のmod結果を格納するリスト
mod1_list = [0]*n
mod2_list = [0]*n

now1 = 1

x = x[::-1]

# mod1の計算
for i in range(n):
    mod1_list[i] = now1
    if x[i] == "1":
        mod1 += now1%(count+1)
    now1 *= 2
    now1 %= (count+1)

mod1 %= (count+1)

now2 = 1

# mod2の計算
if count >= 3:
    for i in range(n):
        mod2_list[i] = now2
        if x[i] == "1":
            mod2 += now2%(count-1)
        now2 *= 2
        now2 %= (count-1)
    
    mod2 %= (count-1)

mod1_list = mod1_list[::-1]
mod2_list = mod2_list[::-1]
x = x[::-1]

for i in range(n):
    total = 1
    if x[i] == "1":
        if count in (1,2):
            print(1)
            continue
        now = mod2-mod2_list[i]
        now %= (count-1)
    else:
        now = mod1+mod1_list[i]
        now %= (count+1)

    while now != 0:
        now = now%(bin(now).count("1"))
        total += 1

    print(total)

Submission status: Wrong Answer

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

count = x.count("1")

mod1 = 0 # 1少ない
mod2 = 0 # 1多い

#　初回の各桁のbitを反転させた場合のmod結果を格納するリスト
mod1_list = [0]*n
mod2_list = [0]*n

now1 = 1

x = x[::-1]

# mod1の計算
for i in range(n):
    mod1_list[i] = now1
    if x[i] == "1":
        mod1 += now1%(count+1)
    now1 *= 2
    now1 %= (count+1)

mod1 %= (count+1)

now2 = 1

# mod2の計算
if count >= 3:
    for i in range(n):
        mod2_list[i] = now2
        if x[i] == "1":
            mod2 += now2%(count-1)
        now2 *= 2
        now2 %= (count-1)
    
    mod2 %= (count-1)

mod1_list = mod1_list[::-1]
mod2_list = mod2_list[::-1]
x = x[::-1]

for i in range(n):
    total = 1
    if x[i] == "1":
        if count in (1,2):
            break
        now = mod2-mod2_list[i]
        now %= (count-1)
    else:
        now = mod1+mod1_list[i]
        now %= (count+1)

    while now != 0:
        now = now%(bin(now).count("1"))
        total += 1

    print(total)

Submission status: Wrong Answer

Solution code:

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

  if N == 1:
    if X.count("1"):
      print(1)
    else:
      print(0)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

  if N == 1:
    if X.count("1"):
      print(1)
    else:
      print(0)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return 0

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return 0

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
a = 0
pw = [0] * n
pw[0] = 1
for i in range(1, n):
    pw[i] = pw[i - 1] * 2
for i in range(n):
    if s[i] == '1':
        a += int(pw[i])
v = bin(a).count('1')
for i in range(n):
    add = int(pw[i])
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = v
    if s[i] == '1':
        x -= 1
    else:
        x += 1
    cnt = 1
    if copy == 0:
        cnt = 0
    while x > 0 and copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

  if N == 1:
    if X == "1":
      print(1)
    else:
      print(0)
    exit()

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return 0

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return 0

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

  if N == 1:
    if X == "1":
      print(1)
    else:
      print(0)
    return 0

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return 0

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return 0

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
a = 0
for i in range(n):
    if s[i] == '1':
        a += int(pow(2, n - i - 1))
v = bin(a).count('1')
for i in range(n):
    add = int(pow(2, n - i - 1))
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = v
    if s[i] == '1':
        x -= 1
    else:
        x += 1
    cnt = 1
    while x > 0 and copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

count = x.count("1")

mod1 = 0 # 1少ない
mod2 = 0 # 1多い

#　初回の各桁のbitを反転させた場合のmod結果を格納するリスト
mod1_list = [0]*n
mod2_list = [0]*n

now1 = 1

x = x[::-1]

# mod1の計算
for i in range(n):
    mod1_list[i] = now1
    if x[i] == "1":
        mod1 += now1%(count+1)
    now1 *= 2
    now1 %= (count+1)

mod1 %= (count+1)

now2 = 1

# mod2の計算
if count >= 3:
    for i in range(n):
        mod2_list[i] = now2
        if x[i] == "1":
            mod2 += now2%(count-1)
        now2 *= 2
        now2 %= (count-1)
    
    mod2 %= (count-1)

mod1_list = mod1_list[::-1]
mod2_list = mod2_list[::-1]
x = x[::-1]

for i in range(n):
    total = 1
    if x[i] == "1":
        now = mod2-mod2_list[i]
    else:
        now = mod1+mod1_list[i]
    while now:
        now = now%(bin(now).count("1"))
        total += 1
    print(total)

Submission status: Wrong Answer

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

  if X == "1":
    print(1)
    return 0

  if X == "0":
    print(0)
    return 0

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return 0

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return 0

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

  if X == "1":
    print(1)
    return True

  if X == "0":
    print(0)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m < pow_2:
        Xi = (X_int-2**(N-i-1))%(base_1_count-1)
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()