Problem:


Score : 400 points

Problem Statement

There are N empty boxes arranged in a row from left to right.
The integer i is written on the i-th box from the left (1 \leq i \leq N).

For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.

We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:

For every integer i between 1 and N (inclusive), the total number of balls contained in the boxes with multiples of i written on them is congruent to a_i modulo 2.

Does there exist a good set of choices? If the answer is yes, find one good set of choices.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

a_i is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If a good set of choices does not exist, print -1.

If a good set of choices exists, print one such set of choices in the following format:

M
b_1 b_2 ... b_M

where M denotes the number of boxes that will contain a ball, and b_1,\ b_2,\ ...,\ b_M are the integers written on these boxes, in any order.

Sample Input 1

3
1 0 0

Sample Output 1

1
1

Consider putting a ball only in the box with 1 written on it.

There are three boxes with multiples of 1 written on them: the boxes with 1, 2, and 3. The total number of balls contained in these boxes is 1.

There is only one box with a multiple of 2 written on it: the box with 2. The total number of balls contained in these boxes is 0.

There is only one box with a multiple of 3 written on it: the box with 3. The total number of balls contained in these boxes is 0.

Thus, the condition is satisfied, so this set of choices is good.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Putting nothing in the boxes can be a good set of choices.



Sample input:
3
1 0 0


Sample output:
1
1

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = [0] * n
#print("dat: {0}".format(dat))
for i in range(n, 0, -1):
    # i-1で参照すること
    #print(i)
    t = 0
    for j in range(0, n // i):
        #print("add:{0}".format( str( ((j+1) * i) -1 )  ))
        t += res[ ((j+1) * i) -1]

    #print("i[{0}]:  t = {1}".format(i, t))

    if t % 2 == 1:
        if dat[i-1] == 1:
            res[i-1] = 0
        else:
            res[i-1] = 1
    else:
        if dat[i-1] == 1:
            res[i-1] = 1
        else:
            res[i-1] = 0

    #print(res[i-1])
    #print("res: {0}".format(res))

#print(res)

c = 0
for i in range(n):
    if res[i] == 1:
        c += 1

resl = []
resc = c
for i in range(n):
    if c == 0:
        break
    if res[i] == 1:
        c -= 1
        resl.append("1")
    else:
        resl.append("0")

print( len(resl) )
if resc !=0:
    print(" ".join(resl))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
b = []

for i in range(N):
	if i > N/2:
		if a[i]==1:
			print(1)
			print(i)
			break;
		else:
			print(-1)
			break;

	else:
		cnt = 0
		for j in range(int(N/(i+1))):
			if a[(i+1)*j]==1:
				cnt += 1
				b.append((i+1)*j+1)

		if cnt%2 == a[i]:
			print(cnt)
			for k in range(cnt):
				print(b[k])
			break;

		else:
			print(-1)
			break;

Submission status: Wrong Answer

Solution code:
import sys

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

N=int(sys.stdin.readline().rstrip())
AList=list(map(int,sys.stdin.readline().split()))

lcmList=[]
for i in range(N):
  if AList[i] == 1:
    lcmList.append(i+1)
    
if len(lcmList)==0:
  print(0)
  exit()
    
lcmNum=lcmList[0]
for i in range(1,len(lcmList)):
  lcmNum=lcm(lcmNum,lcmList[i])
  
if AList[0]==1 and lcmNum <= N:
  print(1)
  print(lcmNum)
  exit()

if AList[0]==0 and lcmNum*2 <= N:
  print(2)
  print("{} {}".format(lcmNum, lcmNum*2))
  exit()
    
print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int,input().split()))

result = [0] * N
for i in range(N):
    if A_list[N-i-1] == 1 and (N-i)*2 >= N:
        result[N-i-1] = 1
    if A_list[N-i-1] == 0 and (N-i)*2 >= N:
        result[N-i-1] = 0
    if A_list[N-i-1] == 1 and (N-i)*2 < N:
        tmp_sum =0
        for r in range(N-i-1,N,N-i):
            tmp_sum +=result[r]
        if  tmp_sum % 2 == 0:
            result[N-i-1] = 1
        if  tmp_sum % 2 == 1:
            result[N-i-1] = 0
    if A_list[N-i-1] == 0 and (N-i)*2 < N:
       tmp_sum =0
       for r in range(N-i-1,N,N-i):
           tmp_sum +=result[r]
       if  tmp_sum % 2 == 0:
           result[N-i-1] = 0
       if  tmp_sum % 2 == 1:
           result[N-i-1] = 1

print(sum(result))
for i,r in enumerate(result):
    if r == 1:
        print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)

def trial_division(n):

    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            d[num] += 1
            n //= num
    if n > 1:
        d[n] += 1

    return

b = [0] * N
cnt = 0
for i in range(N, 0, -1):
    if d[i] % 2 == 1 and a[i-1] == 0:
        b[i-1] = 1
        cnt += 1
        trial_division(i)
    elif d[i] % 2 == 0 and a[i-1] == 1:
        b[i-1] = 1
        cnt += 1
        trial_division(i)

print(cnt)
for i in range(N):
    if b[i] == 1:
        print(i+1,end=' ')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))

M = [0 for _ in range(N)]
for i in range(N-1, -1, -1):
    total = 0
    n = 2
    while (i+1) * n <= N:
        total += A[(i+1)*n-1]
        n += 1

    if A[i] + total % 2 == A[i]:
        M[i] = A[i]
    else:
        print(-1)
        exit()

print(sum(M))

kugiri = False
for i in range(len(M)):
    if M[i] == 1:
        if kugiri:
            print(" ", end="")
        print(i+1, end="")
        kugiri = True
print()

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
sum_ = sum(arr)

if sum_ == 0:
	print(0)
else:
	output = []

	for i in range(1, n + 1):
		total = 0
		for j in range(i, n + 1, i):
			total += arr[j - 1]

		if total != 0 and (total - arr[i - 1]) % 2 == 0:
			output.append(i)

	if output == []:
		print(-1)
	else:
		print(len(output))
		for i in output:
			print(i, end=' ')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def main():
    # # 整数の入力
    # a = int(input())
    # # スペース区切りの整数の入力
    # b, c = map(int, input().split())
    # # 文字列の入力
    # s = input()
    # # 出力
    # print("{} {}".format(a+b+c, s))
    N = int(input())
    a_list = [int(i) for i in input().split()]
    b_list = [0] * N
    ret_b = []

    # a_listの後ろから順に検討していき，箱にボールをいれるかどうかが
    # 決定していく
    for i, a in enumerate(a_list[::-1]):
        index = N - 1 - i # N-1 --> 0
        ball_sum = get_sum(index, b_list)
        if ball_sum % 2 != a:
            b_list[index] = 1
            ret_b.append(index + 1)
    print(len(ret_b))
    print(' '.join(map(str, ret_b)))




def get_sum(index, b_list): # index: 0-(N-1)
    index_ = index + 1
    cur = index_
    ret_sum = 0
    while (cur<len(b_list)):
        ret_sum += b_list[cur-1]
        cur += index_
    return ret_sum


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = list(map(int, input().split()))

b = [-1 for _ in range(n+1)]
k = 2

for i in range(n, 0, -1):
    if i <= n / k:
        sum = 0
        for j in range(i+i,n+1, i):
            sum = (sum + b[j]) % 2
        if sum == a[i-1]:
            b[i] = 0
        else:
            b[i] = 1
        k += 1
    else:
        b[i] = a[i-1]

m = b.count(1)
print(m)
if m == 0:
    sys.exit()

resb = list(map(lambda y: y[1], filter(lambda x: x[1] > 0, zip(range(n+1), b))))
print(*resb)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
b = []

for i in range(N):
	if i > N/2:
		if a[i]==1:
			print(1)
			print(i)
			break;
		else:
			print(-1)
			break;

	else:
		cnt = 0
		for j in range(int(N/(i+1))):
			if a[(i+1)*j]==1:
				cnt += 1
				b.append((i+1)*j)

		if cnt%2 == a[i]:
			print(cnt)
			for k in range(cnt):
				print(b[k])
			break;

		else:
			print(-1)
			break;

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
for i in reversed(range(n)):
    count=0
    for j in range(i+1,n+1):
        if j%(i+1)==0:
            count+=a[j-1]
    if count%2==1:       
        b.append(1)
        
if len(b)>0:       
  for _ in range(len(b)):
  	print("1")
else:
  print("0")

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int, input().split()))
n=N//2
b=[None]*N
for i in range(n,N):
        b[i]=a[i]
for i in range(n-1,0,-1):
        c=0
        t=i
        while t<N:
                if b[t]==1:
                        c+=1
                t+=i+1
        b[i]=(c+a[i])%2
M=b.count(1)
if a[0]==0:
        b[0]=M%2
else:
        b[0]=(M+1)%2
if b[0]==1:
        print(M+1)
else:
        print(M)
for i in range(N):
        if b[i]==1:
                print(i+1,end=" ")

Submission status: Wrong Answer

Solution code:
n=input()
arr=[0]+map(int,raw_input().split())
b=[0]*(n+1)
m=0
ans=True
for i in range(n,0,-1):
    s=0
    for j in range(i,n+1,i):
        s+=arr[j]
    if s%2==arr[i]:
        b[i]=arr[i]
        if arr[i]==1:
            m+=1
    else:
        b[i]=arr[i]^1
        if arr[i]==0:
            m+=1
if arr==b:
    print m
    print '1 '*m
else:
    print 0

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if 1 in A[1:]:
	print(-1)
else:
	if A[0] == 0:
		print(0)
	else:
		print(1)
		print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())
a_l = list(map(int,input().split()))
ans_l = {}
for i,a in enumerate(a_l[::-1]):
    index = N-i
    curnum = 0
    for j in range(2,N//2):
        if(index*j<=N):
           curnum += ans_l[index*j]
        else:
            break
    if(curnum%2!=a):
        ans_l[index] = 1
    else:
        ans_l[index] = 0

ans_str = ""
ans_len = 0
for key,num in ans_l.items():
    if(num==1):
        ans_str+=str(key)+" "
        ans_len+=1

print(ans_len)
if(ans_str != ""):
    print(ans_str[:-1])

Submission status: Wrong Answer

Solution code:
def primes(x):
  is_prime = [True] * (x + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(x**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, x + 1, i):
      is_prime[j] = False
  return [i for i in range(x + 1) if is_prime[i]]

n=int(input())
P=primes(n)
pp=len(P)
A=[int(i) for i in input().split()]
Ans=[]
C=[False]*n
for i in reversed(range(n)):
  if A[i]==1:    
    if 2*(i+1)>n:
      Ans.append(i+1)
      C[i]=True
    else:
      c=1
      j=0
      while j<pp and P[j]*(i+1)<=n:
        if C[P[j]*(i+1)-1]==True:
          c^=1
        j+=1
      if c==1:
        Ans.append(i+1)
        C[i]=True
  elif A[i]==0:    
    c=0
    j=0
    while j<pp and P[j]*(i+1)<=n:
      if C[P[j]*(i+1)-1]==True:
        c^=1
      j+=1
    if c==1:
      Ans.append(i+1)
      C[i]=True
if len(Ans)==0:
  print(0)
else:
  print(len(Ans))
  Ans.sort()
  print(*Ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
NN = N
bit = [0]*N
N = len(a)
while N > 0:
    yakusu = make_divisors(N)
    if a[N-1] == 1:
        for i in yakusu:
            bit [i-1] = bit[i-1] + 1
            if bit[i-1] == 2:
                bit[i-1] = 0
    N = N-1

if bit == a:
    print(sum(bit))
    STR = ""
    for i in range(NN):
        if bit[i] == 1:
            STR = STR + str(i+1)+" "
    print(STR)
elif sum(bit) != 0:
    print(-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
mainsum = sum(a)
if mainsum == 1 and a[0] == 1:
    print('1\n1')
elif mainsum == 0:
    print('0')
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [int(elem) for elem in input().split()]
id_lst = [i + 1 for i, elem in enumerate(a_lst) if elem == 1]

flag = 0
for i in id_lst:
    cnt = 0
    for j in range(n // i + 1) :
        if j in id_lst:
            cnt += 1
    if cnt % 2 == 0:
        flag = -1
        break

if flag == 0:
    print(len(id_lst))
    if len(id_lst) != 0:
        id_lst = list(map(str, id_lst))
        print(' '.join(id_lst))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def make_divisors(n):
  if n == 1:
    return [1]
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors

N = I()
a = IL()
cnt = [0]*N

ans = ""
M = 0
for i in range(N):
  if cnt[i]%2 == 0 and a[i] == 1 or cnt[i]%2 == 1 and a[i] == 0:
    M += 1
    ans += str(i+1) + " "
  if a[i] == 1:
    l = make_divisors(i+1)
    for j in l:
      cnt[j-1] += 1

if ans == "":
  print(0)
else:
  print(M)
  print(ans[:-1])

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    al = [0] + list(map(int, input().split()))

    count = 0
    nums = set()
    for i in range(1, n+1):
        l = al[i+i::i]
        if sum(l) % 2 != al[i]:
            count += 1
            nums.add(i)

    print(count)
    [print(i) for i in nums]

Submission status: Wrong Answer

Solution code:


n = input()
li = list(map(int,input().split()))
flag = True
count = 0
one = []
for i in range(len(li)) :
    if(li[i] == 1):
        count += 1
        one.append(i + 1)
    j = i
    sum = 0
    while(j < len(li)):
        sum += li[j]
        j += (i+1)
    sum %= 2
    if(li[i] != sum):
        flag = False
        break

if(flag == False):
    print(-1)
else:
    print(count)
    if(count != 0):
        print(*one)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    l = []
    for i in range(1, N+1):
        l.append(i)

    ans = []

    for i in range(N):
        idx = l[i]
        x = A[idx-1::idx]
        if sum(x) % 2 == A[i]:
            if A[i] == 1:
                ans.append(idx)
        else:
            print(-1)
            return

    if len(ans) > 0:
        print(len(ans))
        print(" ".join(map(str, ans)))
    else:
        print(0)

resolve()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
if n==1:
  print(1)
  print(l[0])
else:
  m=0
  ans=[]
  for i in range(1,n+1)[::-1]:
    r=0
    for h in ans:
      if int(h)%i==0:
        r+=1
    if r%2!=l[i-1]:
      m+=1
      ans.append(str(i))
  print(m)
  print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A_index = [i+1 for i in range(N) if A[i] == 1]


a = [len(["a" for i in A_index if i % (j+1)== 0]) %2 for j in range(N)]
if a == A:
    print(sum(a))
    a_index = [i+1 for i in range(N) if a[i] == 1]
    for i in range(sum(a)):
        print(a_index[i] ,end='')
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))

result = []
res_ap = result.append

for i in range(N // 2, N)[::-1]:
    if a[i] == 1:
        res_ap(i)
for i in range(N // 2)[::-1]:
    j = 2 * (i + 1)
    while(j < N + 1):
        cnt = 0
        cnt += a[j - 1]
        j += i + 1
    if a[i] + cnt % 2 == 1:
        res_ap(i)
M = len(result)
print(M)
if M != 0:
    print(result[0] + 1, end = "")
    for i in range(1, M):
        print(" " + str(result[i] + 1), end = "")

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = list(map(int,input().split()))
 

half_N = (N // 2)
a = np.array(a)
a_half = a[half_N:]

ans = np.array(np.where(a_half == 1))
ans += (half_N+1)
ans.flatten()

ans = np.array(ans)


N_ = half_N + 1
while N_ > 0:
	if (np.count_nonzero(ans % N_ == 0) % 2) != a[N_ - 1]:
		ans = np.append(ans,N_)
	N_ -= 1
 
print(len(ans))
for i in ans:
	print(i,end = " ")

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
b = []

for i in range(N):
	if i > N/2:
		if a[i]==1:
			print(1)
			print(i)
			break;
		else:
			print(-1)
			break;

	else:
		cnt = 0
		for j in range(int(N/(i+1))):
			if a[(i+1)*j]==1:
				cnt += 1
				b.append(a[(i+1)*j])

		if cnt%2 == a[i]:
			print(cnt)
			for k in range(cnt):
				print(b[k])
			break;
			
		else:
			print(-1)
			break;

Submission status: Wrong Answer

Solution code:
N=int(input())
a =list(map(int, input().split()))
b=[]
c=[]
for x in range(N):
    b.append(0)
for z in range(0,N-1):
    if z!=0:
        a=b
    for x in range(1,N+1):
        X=0
        for y in range(1,N+1):
            if y%x==0 and a[y-1]==1:
                X=X+1
            if y%x==0 and a[y-1]==0:
                X=X
        b[x-1]=X%2
print(b.count(1))
if b.count(1)!=0:
    for x in range(N):
        if b[x]==1:
            c.append(x+1)
    L=[str(k) for k in c]
    L=" ".join(L)
    print(L)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = []
ans = 0
for i in reversed(range(1, N+1)):
    j = 2
    count = 0
    while True:
        if i*j <= N:
            count += a[i*j-1]
            j += 1
        else:
            break
    if (a[i-1] % 2 == 0 and count%2 == 1) or (a[i-1] % 2 == 1 and count%2 == 0):
        b.append(i)
        ans += 1
    

b.reverse()
print(ans)
if ans != 0:
    print(*b)

Submission status: Wrong Answer

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


def make_divisors(n):
  divisors = []
  for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n // i)

  # divisors.sort()
  return divisors


test_str = '''
100
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()
  li = IN_L_I()

  tmp = [False] * n

  for i, b in enumerate(reversed(li)):
    ci = n - i - 1
    # print("hoge:",i,b,ci)
    if b == 1 and not tmp[ci]:
      tmp[ci] = True

    if b == 0 and tmp[ci]:
      tmp[ci] = False

    if b == 1:
      for j in make_divisors(ci + 1):
        if j != ci + 1:
          tmp[j] = not tmp[j]

    # print(tmp)

  puts = [i * 1 for i, x in enumerate(tmp) if x]
  print(len(puts))
  if len(puts) > 0:
    print(" ".join([str(i + 1) for i in puts]))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n // 2 + 2):
    if sum(a[n // 2 - i + 1::i]) % 2 == a[n // 2 - i]:
        a[n // 2 - i] = 0
    else:
        a[n // 2 - i] = 1
b = []
cnt = 0
for i in a:
    if a[i] == 1:
        b.append(str(i + 1))
        cnt += 1
if cnt != 0:
    print(cnt)
    print(' '.join(b))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(raw_input())
a=map(int, raw_input().split())

b=[0]*n
for i in range(n,0,-1):
    v=0
    for j in range(i,n+1,i):
        v+=b[j-1]
    b[i-1]=1 if v%2!=a[i-1] else 0
m=b.count(1)
print m
for i in range(m):
    print "1",
print ""

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))

ANS = [0 for i in range(n)]
for i in range(n,0,-1):
    k = n//i
    su = 0
    #print(i)
    #print((i,i**k+i,i))
    for j in range(i,i*k+i,i):
        su += ANS[j-1]
    if su!=A[i-1]:
        ANS[i-1] += 1

#print(ANS)

print(sum(ANS))
for i in range(len(ANS)):
    if ANS[i]==1:
        print(i+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = list(map(int, input().split()))

b = [0] * n

for i in range(n-1, -1, -1):
    b[i] = a[i] + 2
    if i ==  0:
        for j in range(1, n):
            b[i] -= b[j]
    elif n//i > 1:
        for j in range(1, n//i-1):
            b[i] -= b[i*(j+1)]
    b[i] = b[i] % 2 + 2


print(n)
print(' '.join(map(str, b)))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
answer = [0]*N
dp = [0]*N

for i in range(N-1, -1, -1):
  if i >= N//2 and a[i] == 1:
    answer[i] = 1
    dp[i] = 1

  if i < N//2:
    if (a[i] == 1 and dp[i*2+1]%2 == 0) or (a[i] == 0 and dp[i*2+1]%2 == 1):
      answer[i] = 1
      dp[i] += dp[i*2]

print(len([i for i in answer  if i == 1]))
not_empty_boxes = [str(index+1) for index, value in enumerate(answer) if value == 1]
if len(not_empty_boxes) > 0:
  print(' '.join(not_empty_boxes))

Submission status: Wrong Answer

Solution code:
import os, sys, re, math

N = int(input())

a = list(map(int,input().split(' ')))

memo = [0 for _ in range(N+1)]

for i in range(N,0,-1):
    temp_s = 0
    m = 1
    while m * i <= N:
        temp_s += memo[m*i]
        m += 1

    memo[i] = (temp_s % 2) ^ a[i-1]

ret = [i for i in range(1,N+1) if memo[i] == 1]
if len(ret) == 0:
    print(0)
else:
    print(sum(ret))
    ret = list(map(str,ret))
    print(' '.join(ret))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a_s = list(map(int, input().split(' ')))
    results = []
    for i, a in enumerate(a_s):
        if sum(a_s[i::(i+1)]) % 2 != a:
            print(-1)
            quit()
        elif a == 1:
            results.append(str(i+1))
    print(len(results))
    if results:
        print(' '.join(results))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def printl(a,b):
    l=[0 for i in range(b)]
    for i in a:
        l[i-1]=1
    for i in l:
        print(i,end=" ")
    print()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
            for j in range(0,cnt):
                arr.append(i**j)
    arr.append(temp)
    arr.append(n)
    return arr
n=input()
n=int(n)
a=[int(i) for i in input().split()]
a2=[i for i in a]
l=[0 for i in range(n)]
ll=[]
if 1 in a:
    of=0
    for i in reversed(a):
        if i==1:
            x=factorization(n-of)
            for j in x:
                l[j-1]+=1
                a[j-1]=0
            ll.append(n-of)
        of+=1
    l=[i%2 for i in l]
    if l==a2:
        print(len(ll))
        printl(ll,n)
    else:
        print(-1)
                
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def factor(n):
    res = []
    for i in range(1, n + 1):
        if n % i == 0:
            res.append(i)
    return res
def get_num(num_arr, a):
    boll_sum = 0
    for p in factor(len(num_arr))[1:]:
        boll_sum += num_arr[p - 1]
    if boll_sum % 2 == a:
        return 0
    else:
        return 1

n = int(input())
bs = [int(x) for x in input().split(" ")]
res = ""
s = 0
bolls = []
for i,a in enumerate(bs):
    boll_count = get_num(bolls, a)
    bolls.append(boll_count)
    if boll_count == 1:
      res += str(i + 1)
    s += boll_count
print(s)
if res:
    print(res)
else:
    print("0")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime_list = primes(N)

dps = [0 for _ in range(N)]

ans =[]
#半分までは確定
fs = N // 2
for i in range(fs, N):
    dps[i] += A[i]
    if A[i] == 1:
        ans.append(i+1)


for i in reversed(range(fs)):
    print(i)
    # 考慮すべき数i*素数 < N
    num = 0
    for p in prime_list:
        if (i+1) * p <= N:
            num += dps[(i+1) * p - 1]

    
    if dps[2 * i] % 2 != num:
        dps[i] += 1
        ans.append(i+1)


if len(ans) != 0:
    print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = tuple(map(int, input().split()))
b = [0] * n
ret = 0
ret2 = []
append = ret2.append
for i in range(n, 0, -1):
  count = 0
  for j in range(i+i, n+1, i):
    count += b[j-1]
  # print((i, count))
  if not (count % 2) == a[i-1]:
    b[i-1] = 1
    ret += 1
    append(i)

# print(b)
print(ret)
if ret == 0:
  exit()

# print(*reversed(ret2))

for i in range(n):
  if b[i] == 1:
    print('%d ' % i, end="")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
mainsum = sum(a)
if mainsum == 1:
    print('1\n1')
elif mainsum == 0:
    print('0')
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = [0] * n
#print("dat: {0}".format(dat))
for i in range(n, 0, -1):
    # i-1で参照すること
    #print(i)
    t = 0
    for j in range(0, n // i):
        #print("add:{0}".format( str( ((j+1) * i) -1 )  ))
        t += res[ ((j+1) * i) -1]

    #print("i[{0}]:  t = {1}".format(i, t))

    if t % 2 == 1:
        if dat[i-1] == 1:
            res[i-1] = 0
        else:
            res[i-1] = 1
    else:
        if dat[i-1] == 1:
            res[i-1] = 1
        else:
            res[i-1] = 0

    #print(res[i-1])
    #print("res: {0}".format(res))

#print(res)

c = 0
for i in range(n):
    if res[i] == 1:
        c += 1

resl = []
resc = c
for i in range(n):
    if c == 0:
        break
    if res[i] == 1:
        c -= 1
        resl.append("1")
    else:
        resl.append("0")

print(len(resl))
if resc !=0:
    print(" ".join(resl))

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    l = []
    for i in range(1, N+1):
        l.append(i)

    ans = []

    for i in range(N):
        idx = l[i]
        x = A[idx-1::idx]
        if sum(x) % 2 == A[i]:
            if A[i] == 1:
                ans.append(idx)

    if len(ans) > 0:
        print(len(ans))
        print(" ".join(map(str, ans)))
    else:
        print(0)
        
resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))

a_count = len(a_list)

boll_list = [0] * n

for rev_index, a in enumerate(reversed(a_list)):
    index = a_count - rev_index - 1
    if (a + 1) * 2 > a_count:
        boll_list[index] = a_list[index]
    else:
        divide_max = a_count // (index + 1)
        total = 0
        for i in range(divide_max):
            total += boll_list[i]
        total = total % 2
        if a_list[index] != total:
            boll_list[index] = 1

if (1 in boll_list):
    output_list = []
    for index, i in enumerate(boll_list):
        if i == 1:
            output_list.append(str(index + 1))
    print(' '.join(output_list))
else:
    print('0')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import sys

def solve(N: int, a: "List[int]"):
    dp = [0] * N
    for i in range(N, 0, -1):
        if i > N // 2:
            dp[i-1] = a[i-1]
        else:
            for j in range(2, N // i):
                dp[i-1] += dp[j * i - 1]
            dp[i-1] += a[i-1]
            dp[i-1] %= 2
    print(sum(dp))
    s = []
    for i in range(N):
        if dp[i] == 1:
            s.append('%d' % (i + 1))
    if len(s) > 0:
        print(' '.join(s))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
sum_ = sum(arr)

if sum_ == 0:
	print(0)
else:
	output = []

	for i in range(1, n + 1):
		total = 0
		for j in range(i, n + 1, i):
			total += arr[j - 1]

		if (total - arr[i - 1]) % 2 == 0:
			output.append(i)

	if output == []:
		print(-1)
	else:
		print(len(output))
		for i in output:
			print(i, end=' ')

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int, input().split()))
n=N//2
b=[None]*N
for i in range(n,N):
        b[i]=a[i]
for i in range(n-1,0,-1):
        c=0
        t=i
        while t<N:
                if b[t]==1:
                        c+=1
                t+=i+1
        b[i]=(c+a[i])%2
M=b.count(1)
if a[0]==0:
        b[0]=M%2
else:
        b[0]=M%2+1
if b[0]==1:
        print(M+1)
else:
        print(M)
for i in range(N):
        if b[i]==1:
                print(i+1,end=" ")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    boxes = [0] * N

    count = 0  
    printlist = []

    count = 0
    printlist = []
    for i in range(N//2,N):
        boxes[i] = A[i]
        if A[i] == 1:
            count = 1
            printlist.append(i)
    for i in range(0,N//2):
        s = A[i]
        for j in range(2,N//(i+1)):
            s ^= boxes[(i+1)*j - 1]
        boxes[i] = s
        if s == 1:
            count += 1

            printlist.append(i)

    import sys
    print(count)
    for i in printlist:
        sys.stdout.write(str(i+1))
        sys.stdout.write(' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

b = [0] * N

for i in range(N):
    for j in range(i + 1, N + 1, i + 1):
        b[i] ^= A[j - 1]

match = True

for i in range(N):
    if A[i] != b[i]:
        match = False
        break

if not match:
    print("-1")
else:
    print(A.count(1))
    for i in range(N):
        if A[i] == 1:
            print(i + 1)