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:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        cnt = 0
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
st = 0
for i in range(n):
    st += int(s[i])
#print(st)
if st == 1:
    for i in range(n):
        if s[i] == '1':
            print(0)
        else:
            print(1)
    exit()
m1 = [1]
p1 = [1]
for i in range(n-1):
   m1.append(m1[-1]*2%(st-1))
   p1.append(p1[-1]*2%(st+1))
if st-1 == 1:
    m1[0] = 0
if st+1 == 1:
    p1[0] = 0
m1.reverse()
p1.reverse()
#print(m1)
#print(p1)
ansm = 0
ansp = 0
for i in range(n):
    ansm += m1[i] * int(s[i])
    ansp += p1[i] * int(s[i])
#print(ansm)
#print(ansp)
time = [0 for _ in range(20)]
def nex(time):
    for i in range(20):
        if time[i] == 0:
            time[i] += 1
            return time
        else:
            time[i] = 0
ans = [0 for _ in range(200001)]
time2 = 1
time[0] = 1
while time2 <= 200000:
    #print(time,time2)
    ans[time2] = ans[time2 % sum(time)] + 1
    time = nex(time)
    time2 += 1
#print(ans[:20])
for i in range(n):
    if s[i] == '1':
        use = (ansm-m1[i]) % (st-1)
    else:
        use = (ansp+p1[i]) % (st+1)
    print(1+ans[use])

Submission status: Wrong Answer

Solution code:
n = int(input())
x = list(input())
c1 = x.count("1")+1
c2 = c1-2

now1 = 0
now2 = 0

for i in range(n):
    if x[-1-i] == "1":
        now1 += pow(2,i,c1)
        if c2 != 0:
            now2 += pow(2,i,c2)
        
    now1 %= c1
    if c2 != 0:
        now2 %= c2

for i in range(n):
    if x[i] == "1":
        #print(n-1-i)
        if c2 == 0:
            print(1)
            continue
        now = (now2-pow(2,n-1-i,c2))%c2
        #print(i,now,c2)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)
    else:
        #print(n-1-i)
        now = (now1+pow(2,n-1-i,c1))%c1
        #print(i,now,c1)
        count = 1
        while now > 0:
            q = bin(now)
            y = q.count("1")
            now %= y
            count += 1
        print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
x = rr()
li = list(x)
for idx in range(n):
    if li[idx] == 1:
        a = x[:idx] + '0' + x[idx+1:]
    else:
        a = x[:idx] + '1' + x[idx+1:]
    t = bin(int(a, 2)).count('1')
    print(bin(t&int(a, 2)).count('1'))

Submission status: Wrong Answer

Solution code:
def main():
    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 = int(input(), 2)
    X_count = popcount(X)

    ans = []
    for i in range(N-1, -1, -1):
        count = 1
        target = 1 << i
        Xi = X ^ target

        if X_count == 1 and target & X:
            ans.append(0)
            continue

        if target & X:
            Xi %= (X_count - 1)
        else:
            Xi %= (X_count + 1)

        # process
        while Xi:
            count += 1
            Xi %= popcount(Xi)

        ans.append(count)
    
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
sX = input()
modX = sX.count('1')
if modX == 0:
    for _ in range(N):
        print(0)
    exit()
elif modX == 1:
    for _ in range(N):
        print(1)
    exit()
else:
    modp = modX + 1
    modm = modX - 1
    sX = sX[::-1]
    Xmodp = 0
    Xmodm = 0
    for i, b in enumerate(sX):
        if b == '1':
            Xmodp += pow(2, i, modp)
            Xmodp %= modp
            Xmodm += pow(2, i, modm)
            Xmodm %= modm
    s = []
    for i, b in enumerate(sX):
        if b == '1':
            s += [(Xmodm - pow(2, i, modm)) % modm]
        else:
            s += [(Xmodp + pow(2, i, modp)) % modp]
    t = s[::-1]

memo = collections.defaultdict(int)
memo[0] = 0
memo[1] = 1


def f(x):
    if x in memo:
        return memo[x]
    else:
        y = x % bin(x).count('1')
        ret = 1 + f(y)
        memo[x] = ret
        return ret


ans = []
for k in t:
    ans += [1 + f(k)]
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
x = map(int,raw_input())
mem = {}

def g(x, mod):
	ximod = 1 % mod
	r = 0
	for i,xi in enumerate(x[::-1]):
		
		if i: ximod *= 2
		ximod %= mod
		if xi == 1:
			r += ximod
			r %= mod
	return r

def rep(r):
	return map(int,bin(r)[2:])
def f(x):
	if all([xi == 0 for xi in x]):
		return 0
	cc =  collections.Counter(x)
	if cc[1] == 1:
		return 1

	if tuple(x) in mem:
		return mem[tuple(x)]
	compute = g(x,cc[1])
	if compute == 0: return 1
	mem[tuple(x)] =  1 + f(rep(compute))
	return mem[tuple(x)]

for i in range(n - 1, -1, -1):
	print f(x[:i] + [1- x[i]] + x[i+1:])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans

pc = sum(item=="1" for item in a)
val0 = 0 # pc-1
val1 = 0 # pc+1
for i in range(n):
    if a[i]=="1":
        if pc>1:
            val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        if pc==1:
            val = 0
        else:
            val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) + 1 #(1<<(n-1-i))
        ans[i] = sub(val)
#         print(1, bin(val)[2:], pc-1)
    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
st = 0
for i in range(n):
    st += int(s[i])
print(st)
if st == 1:
    for i in range(n):
        if s[i] == '1':
            print(0)
        else:
            print(1)
    exit()
m1 = [1]
p1 = [1]
for i in range(n-1):
   m1.append(m1[-1]*2%(st-1))
   p1.append(p1[-1]*2%(st+1))
if st-1 == 1:
    m1[0] = 0
if st+1 == 1:
    p1[0] = 0
m1.reverse()
p1.reverse()
#print(m1)
#print(p1)
ansm = 0
ansp = 0
for i in range(n):
    ansm += m1[i] * int(s[i])
    ansp += p1[i] * int(s[i])
#print(ansm)
#print(ansp)
time = [0 for _ in range(20)]
def nex(time):
    for i in range(20):
        if time[i] == 0:
            time[i] += 1
            return time
        else:
            time[i] = 0
ans = [0 for _ in range(200001)]
time2 = 1
time[0] = 1
while time2 <= 200000:
    #print(time,time2)
    ans[time2] = ans[time2 % sum(time)] + 1
    time = nex(time)
    time2 += 1
print(ans[:20])
for i in range(n):
    if s[i] == '1':
        use = (ansm-m1[i]) % (st-1)
    else:
        use = (ansp+p1[i]) % (st+1)
    print(1+ans[use])

Submission status: Wrong Answer

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

nxt = [0]*n
zero2one = 0
one2zero = 0

cnt = 0
for i in range(n):
    if x[i]=='1':
        cnt += 1

zero2one = 0
for i in range(n):
    zero2one += int(x[i])*pow(2,n-i-1,cnt+1)
zero2one %= cnt+1

one2zero = 0
if cnt>1:
    for i in range(n):
        one2zero += int(x[i])*pow(2,n-i-1,cnt-1)
    one2zero %= cnt-1

for i in range(n):
    if x[i]=='0':
        nxt[i] = (zero2one + pow(2,n-i-1,cnt+1))%(cnt+1)
    else:
        if cnt>1:
            nxt[i] = (one2zero - pow(2,n-i-1,cnt-1))%(cnt-1)
        else:
            nxt[i] = 0

MX = 2*10**5+5
ans = [0]*MX
for i in range(MX):
    xn = bin(i)[2:]
    res = 0
    while(xn != '0'):
        l = len(xn)
        res += 1
        cnt = 0
        for j in range(l):
            if xn[j]=='1':
                cnt += 1
        after = 0
        for j in range(l):
            after += int(xn[j])*pow(2,l-j-1,cnt)
            after %= cnt
        xn = bin(after)[2:]
    ans[i]=res

for i in range(n):
    print(ans[nxt[i]]+1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    X = input()
    MOD = 0
    for elem in X:
        if elem == '1':
            MOD += 1
    if MOD == 0:
        print("1" + "\n1" * (N-1))
        return 0
    if MOD == 1 and X[-1] == '1':
        print("2\n" * (N-1) + "0")
        return 0
    if MOD == 1 and X[-1] == '0':
        ans = ''
        for i in range(N):
            if X[i] == '1':
                ans += '0'
            else:
                ans += '1'
            if i != N-1:
                ans += '\n'
        print(ans)
        return 0
    MODP1 = MOD + 1
    MODM1 = MOD - 1
    POWEROFTWOP1 = [0] * N
    POWEROFTWOM1 = [0] * N
    POWEROFTWOP1[0] = 1
    POWEROFTWOM1[0] = 1
    for i in range(1,N):
        POWEROFTWOP1[i] = (POWEROFTWOP1[i-1] * 2) % MODP1
        POWEROFTWOM1[i] = (POWEROFTWOM1[i-1] * 2) % MODM1
    xMODP1 = 0
    xMODM1 = 0
    for i in range(N):
        if X[i] == '1':
            xMODP1 += POWEROFTWOP1[N - i - 1]
            xMODM1 += POWEROFTWOM1[N - i - 1]
    xMODP1 %= MODP1
    xMODM1 %= MODM1
    ans = ""
    for i in range(N):
        if X[i] == '0':
            anscur = xMODP1
            anscur += POWEROFTWOP1[N - i - 1]
            anscur %= MODP1
        if X[i] == '1':
            anscur = xMODM1
            anscur -= POWEROFTWOM1[N - i - 1]
            anscur %= MODM1
        cnt = 1
        while anscur != 0:
            ans2 = bin(anscur)[2:]
            oneCount = 0
            for elem in ans2:
                if elem == '1':
                    oneCount += 1
            anscur %= oneCount
            cnt += 1
        ans += str(cnt)
        if i != N-1:
            ans += '\n'
    print(ans)
                    
main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(2000)

X = input()
Y = int(X,2)
@lru_cache(maxsize=None)
def f(x):
    counter = 0
    a = x
    while a>0:
        a = x % bin(a).count("1")
        counter += 1
    return counter 


for i in range(N):
    k = int(X[i])
    if k == 0:
        Z = Y + pow(2,N-i-1)
    else:
        Z = Y - pow(2,N-i-1)
    
    print(f(Z))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

from functools import lru_cache

def popcount1(n):
    ans = 0
    while n > 0:
        ans += n & 1
        n //= 2
    return ans

bit = {}
@lru_cache(maxsize=None)
def popcount2(bits):
    if bits in bit:
        return bit[bits]

    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
    ans = (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff)
    bit[bits] = ans
    return bit[bits]


memo = {0: 0}
@lru_cache(maxsize=None)
def rec(n):
    if n in memo:
        return memo[n]
    
    p = popcount2(n)
    new_n = n % p
    ans = rec(new_n) + 1
    memo[n] = ans
    return memo[n]


def submit():
    n = int(input())
    x = input()
    x = int('0b' + x, 0)

    ans = []
    base_bit = popcount1(x)
    bit[x] = base_bit
    for i in range(1, n + 1):
        mask = 1 << (n - i)
        xi = x ^ mask
        if x & mask:
            bit[xi] = bit[x] - 1
        else:
            bit[xi] = bit[x] + 1
        ans.append(rec(xi))

    for a in ans:
        print(a)


if __name__ == "__main__":
    submit()

Submission status: Wrong Answer

Solution code:
def popcount(n):
    ans=0
    for i in range(20):
        if n>>i & 1:
            ans+=1
    return ans

N=int(input())
X=input()
n=0

for i in range(N):
    if X[i]=='1':
        n+=1
np1=0
nm1=0
temp1=1
temp2=1
np=n+1
nm=n-1
if nm==0:
    nm=1
for i in range(N-1,-1,-1):
    if X[i]=='1':
        np1=(np1+temp1)%np
        nm1=(nm1+temp2)%nm
    temp1=(temp1*2)%np
    temp2=(temp2*2)%nm
    
for i in range(N):
    ans=1
    if X[i]=='1':
        if n==1:
            print(0)
            continue
        temp=(nm1-pow(2,(N-1-i),nm))%nm
        while temp>0:
            ans+=1
            pop_n=popcount(temp)
            if pop_n==0:
                break
            temp=temp%pop_n
    elif X[i]=='0':
        temp=(np1+pow(2,(N-1-i),np))%np
        while temp>0:
            ans+=1
            pop_n=popcount(temp)
            if pop_n==0:
                break

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans

pc = sum(item=="1" for item in a)
val0 = 0 # pc-1
val1 = 0 # pc+1
for i in range(n):
    if a[i]=="1":
        if pc>1:
            val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        if pc==1:
            val = 0
        else:
            val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(1, bin(val)[2:], pc-1)
    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N=int(sys.stdin.readline())
    X=sys.stdin.readline()

    no=X.count('1')
    np=no+1
    nm=no-1
    nm_flag=bool(nm)

    np_mods=[-1]*N
    nm_mods=[-1]*N
    
    np_mods[0]=1
    nm_mods[0]=1
    
    for i in range(1,N):
        np_mods[i]=(np_mods[i-1]*2)%np
        if nm_flag:
            nm_mods[i]=(nm_mods[i-1]*2)%nm

    np_mods.reverse()
    nm_mods.reverse()
    
    np_mods_sum=0
    nm_mods_sum=0
    for i in range(N):
        if X[i]=='1':
            np_mods_sum+=np_mods[i]
            nm_mods_sum+=nm_mods[i]

    for i in range(N):
        if X[i]=='0':
            n=(np_mods_sum+np_mods[i])%np

        else:
            if nm_flag:
                n=(nm_mods_sum-nm_mods[i])%nm
            else:
                print(1)
                continue
        if n==0:
            print(1)
            continue
        count=1
        while True:
            bs=str(bin(n))[2:]
            k=bs.count('1')
            n=n%k
            count+=1
            if n==0:
                break
        print(count)

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = int(in_s(), 2)

    #t = '1101101010' * 10**4
    #X = int(t, 2)
    #N = 10**4

    d = defaultdict(int)

    ans = [0] * N
    for i in range(N):
        a = X ^ (1 << N - i - 1)
        a = bin(a)[2:]

        count = 0
        while int(a, 2):
            if d[a] != 0:
                ans[i] = d[a]
                break
            a = bin(int(a, 2) % a.count('1'))[2:]
            count += 1
        else:
            ans[i] = count

            a = X ^ (1 << N - i - 1)
            a = bin(a)[2:]
            t = 0
            while int(a, 2):
                d[a] = count - t
                a = bin(int(a, 2) % a.count('1'))[2:]
                t += 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    x = input()
    count = 0
    sub = 1
    last = [[0, 0]]*n
    for i in range(n):
        if x[i] == "1":
            count += 1
            
    if count == 0:
        for i in range(n):
            print(1)
        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):
        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^last[n-1-i][0]+count-1)%(count-1)
            print(1+key[judge])
        else:
            judge = (num2^last[n-1-i][1]+count+1)%(count+1)
            print(1+key[judge])

if __name__ == "__main__":
    main()