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

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)

Submission status: Wrong Answer

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

  base_1_count = X.count("1")
  if X == "1":
    print(1)
    return True

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

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

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 = int((X_int_m + pow_2) / 2)
      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 popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

n = int(input())
X = input()
po = X.count('1')
pp = po + 1
pm = max(1, po - 1)
rp = rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm
bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1, 0, -1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm
for i in range(n):
    if X[i] == '0': ri = (rp + bp[i]) % pp
    else: ri = (rm - bm[i]) % pm
    print(f(ri) + (0 if po-1==0 else 1))

Submission status: Wrong Answer

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

def popCount(n):
  count = 0
  while n > 0:
    if n % 2:
      count += 1
    n = n // 2
  return count

def f(n):
  count = 0
  while n != 0:
    n = n % popCount(n)
    count += 1
  return count

x = 0
for i in xs:
  x = x*2 + int(i)

for i in range(n):
  t = x + (1 << (n - 1 - i)) * -1 if xs[i] == "1" else 1
  print(f(t))

Submission status: Wrong Answer

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

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

if po == 0:
    print(0)
    exit()

pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: # '1'
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
        # ri = (rm - bm[i]) % pm
    debug('i {} ri {}'.format(i,ri))
    # if ri == 0:
    #     print(0)
    #     continue
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Wrong Answer

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

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

if po == 0:
    print(0)
    exit()

pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: # '1'
        if po-1 != 0: ri = (rm - bm[i]) % pm
        else:
            print(0)
            continue
        # ri = (rm - bm[i]) % pm
    debug('i {} ri {}'.format(i,ri))
    # if ri == 0:
    #     print(0)
    #     continue
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

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
      Xi = X_int_m - 2**(N-i-1)%(base_1_count-1)
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)

    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:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)

n = int(input())
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

if po == 0:
    print(0)
    exit()

pp = po + 1
pm = max(1, po - 1)

rp = 0
rm = 0
for x in X:
    rp = (rp*2 + int(x)) % pp
    rm = (rm*2 + int(x)) % pm

bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
bp[n-1] = 1 % pp
bm[n-1] = 1 % pm
for i in range(n-1,0,-1):
    bp[i-1] = bp[i]*2 % pp
    bm[i-1] = bm[i]*2 % pm

debug('po {}'.format(po))
debug('pp {}'.format(pp))
debug('pm {}'.format(pm))
debug('rp {}'.format(rp))
debug('rm {}'.format(rm))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % pp
    else: # '1'
        if po-1 == 0: ri = 0
        else: ri = (rm - bm[i]) % pm
    debug('ri {}'.format(ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Wrong Answer

Solution code:
def popcount(n):
    return bin(n).count('1')
N=int(input())
X=input()
xl=list(X)
X=int(X,2)
a=popcount(X)
#1が減った時
if a==1:
    xi=0
else:
    xi=X%(a-1)
#1が増えたとき
xd=X%(a+1)

for i in range(N):
    if xl[i]=='1':
        if a==1:
            print(0)
            continue
        else:
            k=pow(2,N-1-i,a-1)
            x=(xd-k)%(a-1)
    else:
        k=pow(2,N-1-i,a+1)
        x=(xi+k)%(a+1)
    count=1
    while x!=0:
        x%=popcount(x)
        count+=1
    print(count)

Submission status: Wrong Answer

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        print(f((Xms - p2s[-i - 1]) % (n1 - 1)) + 1)
    else:
        print(f((Xms - p2l[-i - 1]) % (n1 + 1)) + 1)

Submission status: Wrong Answer

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

n = int(input())
# X = [int(x) for x in input()]
X = input()
debug('n {}'.format(n))
debug('X {}'.format(X))
po = X.count('1')

if po == 0:
    print(0)
    exit()

ro = 0
rp = 0
rm = 0
for x in X:
    ro = (ro*2 + int(x)) % (po)
    rp = (rp*2 + int(x)) % (po+1)
    rm = (rm*2 + int(x)) % (max(1,po-1))

b = [0]*(n) # 2^i
bp = [0]*(n) # 2^i % (po+1)
bm = [0]*(n) # 2^i % (po-1)
b[n-1] = 1 % (po)
bp[n-1] = 1 % (po+1)
bm[n-1] = 1 % (max(1,po-1))
for i in range(n-1,0,-1):
    b[i-1] = b[i]*2%(po)
    bp[i-1] = bp[i]*2%(po+1)
    bm[i-1] = bm[i]*2%(max(1,po-1))

debug('po {}'.format(po))
debug('ro {}'.format(ro))
debug('rp {}'.format(ro))
debug('rm {}'.format(ro))
debug('b {}'.format(b))
debug('bp {}'.format(bp))
debug('bm {}'.format(bm))
debug('===')

def popcount(x):
    c = 0
    while x > 0:
        if x & 1: c += 1
        x //= 2
    return c

def f(x):
    if x==0: return 0
    return f(x % popcount(x)) + 1

for i in range(n):
    if X[i] == '0':
        ri = (rp + bp[i]) % (po+1)
    else: # '1'
        ri = (rm - bm[i]) % (max(1,po-1))
    debug('ri {}'.format(ri))
    c = f(ri) + 1
    debug('c {}'.format(c))
    print(c)

Submission status: Wrong Answer

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

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

p = popcount(x)
nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= popcount(i)

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        print(0)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
            else:
                mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
                x3 = modx_minus - mod_e
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))
    while Xim > 0:
        Xim % bin(Xim).count("1")
        cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

num_of_one = X.count("1")
X_num = int(X, 2)

X_mod_s = (X_num % (num_of_one - 1)) if num_of_one > 1 else 0
X_mod_l = X_num % (num_of_one + 1)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    two_pow = 2 ** (N - i - 1)
    Xi_mod = 0

    if X[i] == "1" and num_of_one == 1:
        print(cnt)
    elif X[i] == "1":
        two_mod = two_pow % (num_of_one - 1)
        Xi_mod = (
            X_mod_s - two_mod
            if X_mod_s - two_mod >= 0
            else ((num_of_one - 1) + (X_mod_s - two_mod))
        )
    else:
        two_mod = two_pow % (num_of_one + 1)
        Xi_mod = (
            X_mod_l + two_mod
            if X_mod_l + two_mod < (num_of_one + 1)
            else (X_mod_l + two_mod - (num_of_one + 1))
        )
    # print("deb", X_mod_s, X_mod_l, two_mod, Xi_mod, num_of_one)
    cnt = f(Xi_mod) + 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        print(0)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
            x3 = modx_minus - mod_e
            if x3 < 0:
                x3 += (xcount1 - 1)
            elif x3 > (xcount1 - 1):
                x3 -= (xcount1 - 1)
            elif x3 == (xcount1 - 1):
                x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = 1
  if base_1_count > 1:
    X_int_m = X_int%(base_1_count - 1)

# 高速化バージョン
  for i in range(N):
    if base_1_count == 1:
      if X[i] == "1":
        print(0)
        continue
        
    if X[i] == "1":
      Xi = X_int_m - 2**(N-i-1)%(base_1_count-1)
    else:
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    for i in range(n):
        print(1)
    exit()
if px==1:
#https://atcoder.jp/contests/aising2020/submissions/15163004
    for i in range(n):
        if x_[i]=="1":
            cur=i
            break
    for i in range(n):
        if i==cur:
            print(0)
    else:
        if i==n-1 or cur==n-1:
            print(2)
        else:
            print(1)
    # for i in range(n):
    #     if int(x_[-i-1]):
    #         print(0)
    #     else:
    #         if not i or int(x_[-1])==1:###
    #             print(2)
    #         else:
    #             print(1)
    exit()
x=int(x_,2)

pow2=[1]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
S = input()

fl = defaultdict(lambda: -1)

def pcnt(x):
    return str(bin(x)).count("1")

def f(x, cnt):
    if x == 0:
        return cnt

    if fl[x] >= 0:
        return fl[x]
    
    ans = f(x%pcnt(x), cnt+1)
    fl[x] = ans
    return ans

pcntx = pcnt(int(S, 2))

for i in range(N):
    if S[i] == "0":
        pc = pcntx+1
    else:
        pc = pcntx-1

    if pc:
        num = (int(S, 2)^2**(N-i-1))%pc
        print(f(num, 1))
    else:
        print(0)

Submission status: Wrong Answer

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

pow2=[1]

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

Submission status: Wrong Answer

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

pow2=[1]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
S = input()

fl = defaultdict(lambda: -1)

def pcnt(x):
    return str(bin(x)).count("1")

def f(x, cnt):
    if x == 0:
        return cnt

    if fl[x] >= 0:
        return fl[x]
    
    ans = f(x%pcnt(x), cnt+1)
    fl[x] = ans
    return ans

pcntx = pcnt(int(S, 2))

for i in range(N):
    if S[i] == "0":
        pc = pcntx+1
    else:
        pc = pcntx-1

    if pc:
        num = (int(S, 2)^2**(N-i-1))%pc
        print(f(num, 1))
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
def f(n) :
    ans=0
    while n>0 :
        ans+=1
        n=n%bin(n).count("1")
    return ans

#----------------------------------------------------------------------------------------
#こちらで実行

def main() :
    n=int(input())
    x=input()

    c1=x.count("1")                                    #初期のpopcount(x)
    cc2=int("0b"+x,0)                                  #初期のn

    if c1==1 :
        for i in range(n) :
            if x[i]=="1" :                             #1を反転させたら1は0個
                print(0)
            else :
                print(f((pow(2,n-i-1,c1+1)+cc2)%(c1+1))+1)  #あらかじめ1回はもう割っておく
        exit()
        
    cc1=int("0b"+x,0)%(c1-1)
    
    for i in range(n) :
        if x[i]=="1" :
            print(f((-pow(2,n-i-1,c1-1)+cc1)%(c1-1))+1)     #あらかじめ1回はもう割っておく
        else :
            print(f((pow(2,n-i-1,c1+1)+cc1)%(c1+1))+1)


#----------------------------------------------------------------------------------------
#

main()

Submission status: Wrong Answer

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

pow2=[1]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
S = input()

fl = defaultdict(lambda: -1)

def pcnt(x):
    return str(bin(x)).count("1")

def f(x, cnt):
    if x == 0:
        return cnt

    if fl[x] >= 0:
        return fl[x]
    
    ans = f(x%pcnt(x), cnt+1)
    fl[x] = ans
    return ans

for i in range(N-1, -1, -1):
    print(f(int(S, 2)^2**i, 0))

Submission status: Wrong Answer

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

pow2=[1]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
S = input()

fl = defaultdict(lambda: -1)

def pcnt(x):
    return str(bin(x)).count("1")

def f(x, cnt):
    if x == 0:
        return cnt

    if fl[x] >= 0:
        return fl[x]+cnt
    
    ans = f(x%pcnt(x), cnt+1)
    fl[x] = ans-1
    return ans

for i in range(N-1, -1, -1):
    print(f(int(S, 2)^2**i, 0))