Problem:


Score : 500 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

A cheetah and a cheater are going to play the game of Nim.
In this game they use N piles of stones.
Initially the i-th pile contains a_i stones.
The players take turns alternately, and the cheetah plays first.
In each turn, the player chooses one of the piles, and takes one or more stones from the pile.
The player who can't make a move loses.

However, before the game starts, the cheater wants to cheat a bit to make sure that he can win regardless of the moves by the cheetah.
From each pile, the cheater takes zero or one stone and eats it before the game.
In case there are multiple ways to guarantee his winning, he wants to minimize the number of stones he eats.

Compute the number of stones the cheater will eat.
In case there is no way for the cheater to win the game even with the cheating, print -1 instead.

Constraints

1 ≤ N ≤ 10^5

2 ≤ a_i ≤ 10^9

Input

The input is given from Standard Input in the following format:

N
a_1
:
a_N

Output

Print the answer.

Sample Input 1

3
2
3
4

Sample Output 1

3

The only way for the cheater to win the game is to take stones from all piles and eat them.

Sample Input 2

3
100
100
100

Sample Output 2

-1



Sample input:
3
2
3
4


Sample output:
3

Submission status: Accepted

Solution code:
import math

N=int(input())
A=[int(input()) for _ in range(N)]
#print(A)

B=0
for a in A:
  B^=a

C=[]
D=[0]*100
for a in A:
  C.append(bin(a^(a-1))[2:])
#print(C)
for c in C:
  D[len(c)]=1
#print(D)

ans=0
while B:
  #print(B,bin(B))
  if D[len(bin(B)[2:])]:
    B^=2**len(bin(B)[2:])-1
    ans+=1
  else:
    ans=-1
    break
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
grundy=0
edible=set()
def solve(grundy, edible):
  ans=0
  while grundy:
    b=(1<<grundy.bit_length())-1
    if b not in edible:
      return -1
    ans+=1
    grundy^=b
  return ans
for a in A:
  grundy^=a
  edible.add(a^(a-1))
print(solve(grundy,edible))

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openC - Cheating Nim
from functools import reduce
from operator import xor


def main():
    # player is second move -> make xor 0
    N, *A = map(int, open(0))
    # A.sort(reverse=1)
    X, changeable, cand = reduce(xor, A), {x ^ (x - 1) for x in A}, []
    while X:
        i = (1 << X.bit_length()) - 1
        cand.append(i)
        X ^= i
    ans = 0
    for i in cand:
        if i in changeable:
            ans += 1
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openC - Cheating Nim
def main():
    # player is second move -> make xor 0
    N, *A = map(int, open(0))
    A.sort(reverse=1)
    ans, x, flg = 0, 0, [0] * 30
    for i in A:
        x ^= i
        p = bin(i ^ i - 1)[::-1].rfind("1")  # rightmost bits of i^i-1
        flg[p] = 1
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  # i-th bit is on
            if flg[i]:  # possible to erase i-th bit of x
                x ^= p - 1
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools, operator
N = int(input())
A = sorted([int(input()) for _ in range(N)])[::-1]
sA = set(a & -a for a in A)
cumxor = list(itertools.accumulate(A, func=operator.xor))[-1]
cnt = 0
for i in range(30, -1, -1):
    if cumxor & 2**i:
        if 2**i in sA:
            cumxor ^= 2**(i + 1) - 1
            cnt += 1
        else:
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
import itertools, operator, collections
N = int(input())
A = sorted([int(input()) for _ in range(N)])[::-1]
sA = set(a & -a for a in A)
cumxor = list(itertools.accumulate(A, func=operator.xor))[-1]
cnt = 0
for i in range(30, -1, -1):
    if cumxor & 2**i:
        if 2**i in sA:
            cumxor ^= 2**(i + 1) - 1
            cnt += 1
        else:
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
LSB = [0]*32
xor = 0
for i in a:
    xor ^= i
    k = (i&-i).bit_length()
    LSB[k-1] += 1
ans = 0
while xor:
    k = xor.bit_length()
    if LSB[k-1] == 0:
        print(-1)
        exit()
    ans += 1
    xor ^= (1<<k) - 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from functools import reduce

N = int(input())

A = [int(x) for x in sys.stdin.read().split()]

xor = reduce(lambda x,y: x^y,A)

can_change = set(x^(x-1) for x in A)

arr = []
while xor:
    x = (1<<xor.bit_length())-1
    arr.append(x)
    xor ^= x

answer = 0
for x in arr:
    if x in can_change:
        answer += 1
    else:
        answer = -1
        break

print(answer)

Submission status: Accepted

Solution code:
import sys


def solve(grundy, edible):
    ans = 0
    while grundy:
        b = (1 << grundy.bit_length()) - 1
        if b not in edible:
            return -1
        ans += 1
        grundy ^= b
    return ans


n = int(input())
grundy = 0
edible = set()
for a in map(int, sys.stdin):
    grundy ^= a
    edible.add(a ^ (a - 1))
print(solve(grundy, edible))

Submission status: Accepted

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  bit=2**i
  mask=2**i-1
  for j in range(n):
    if (arr[j])&(bit)!=0:
      cnt+=1
      if arr[j]==bit:
        pos=j
    arr[j]&=mask
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=mask
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

Submission status: Accepted

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import xor

N, *A = map(int, open(0).read().split())
x = reduce(xor, A)

memo = set(a ^ (a - 1) for a in A)

ans = 0
K = x.bit_length()
for k in reversed(range(K)):
    if (x >> k) & 1:
        t = (2 << k) - 1
        if t in memo:
            x ^= t
            ans += 1

if x == 0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import xor

N, *A = map(int, open(0).read().split())

x = reduce(xor, A)

ans = 0
K = x.bit_length()
for k in reversed(range(K)):
    if (x >> k) & 1:
        for a in A:
            t = a ^ (a - 1)
            if t == 2 ** (k + 1) - 1:
                x ^= t
                ans += 1
                break

if x == 0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
xor = 0
rank = [0] * 35 
for i in range(n):
    a = int(input())
    LSB = (a & -a).bit_length()
    rank[LSB] += 1
    xor ^= a 

prev = False 
ans = 0
for i in range(33, -1, -1):
    bit = xor & (1 << i)
    if (bit > 0 and prev == 0) or (bit == 0 and prev > 0):
        if rank[i+1] == 0:
            print(-1)
            exit()
        else:
            ans += 1
    prev = bit
print(ans)

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openC - Cheating Nim
import sys
input = sys.stdin.readline


def main():
    # player is second move -> make xor 0
    N = int(input())
    A = sorted(map(int, [input() for _ in range(N)]), reverse=1)
    ans, x, flg = 0, 0, [0] * 30
    for i in A:
        x ^= i
        p = bin(i ^ i - 1)[::-1].rfind("1")
        flg[p] = 1
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  # i-th bit is on
            if flg[i]:  # possible to erase i-th bit of x
                x ^= p - 1
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-exhibition-final-openC - Cheating Nim
import sys
input = sys.stdin.readline

from functools import reduce
from operator import xor


def main():
    # player is second move -> make xor 0
    N = int(input())
    A = sorted(map(int, [input() for _ in range(N)]), reverse=1)
    ans, x = 0, reduce(xor, A)
    # cand := rightmost bits of i^i-1
    cand = set(bin(i ^ i - 1)[::-1].rfind("1") for i in A)
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  # i-th bit is on
            if i in cand:  # possible to erase i-th bit of x
                x ^= (p - 1)
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,*A=map(int,open(0))
x=0
B=[]
for a in A:
	x^=a
	B+=a^a-1,
z=0
k=2**30
for b in sorted(B)[::-1]:
	while k and not(x&k):
		k//=2
	if b&k and b<2*k:
		x^=b
		z+=1
print(-1if x else z)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0))
x=0
c=[0]*30
for i in a:
  x^=i
  c[bin(i^i-1)[::-1].rfind('1')]=1
a=0
for i in range(29,-1,-1):
  if x&2**i:
    if c[i]:
      a+=1
      x^=2**i-1
    else:
      print(-1)
      break
else:
  print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
gr = 0
for x in a:
	gr ^= x
exist = set()
for i in range(n):
	cnt = 0
	while (a[i]>>cnt)&1 == 0:
		cnt += 1
	exist.add(cnt)
ok = True
ans = 0
for i in range(35, -1, -1):
	if (gr>>i)&1:
		if i not in exist:
			ok = False
		else:
			gr %= (1<<(i+1))
			gr = (1<<(i+1)) - gr - 1
			ans += 1
	else:
		gr %= (1<<(i+1))
if ok:
	print(ans)
else:
	print(-1)

Submission status: Accepted

Solution code:
N=int(input())
x=0
A=[0]*N
from collections import defaultdict
cnt=defaultdict(int)
for i in range(N):
    a=int(input())
    x^=a
    cnt[a^(a-1)]+=1
two=[1]*31
for i in range(1,31):
    two[i]=two[i-1]*2
ans=0
for i in range(30,0,-1):
    if ans<0:
        break
    if x%two[i]//two[i-1]==1:
        if cnt[two[i]-1]>0:
            ans+=1
            x^=two[i]-1
        else:
            ans=-1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys, collections

def solve():
    file = sys.stdin.readline
    N = int(file())
    mindig = collections.defaultdict(int)
    nim = 0
    for i in range(N):
        a = int(file())
        nim ^= a
        mindig[a^(a-1)] += 1
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if int(nim[i]) != flip % 2:
                if mindig[pow(2, 30-i) - 1] == 0:
                    print(-1)
                    break
                else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, collections

def solve():
    file = sys.stdin.readline
    N = int(file())
    A = [None] * N
    mindig = collections.defaultdict(int)
    nim = 0
    for i in range(N):
        a = int(file())
        A[i] = a
        nim ^= a
        mindig[a^(a-1)] += 1
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if int(nim[i]) != flip % 2:
                if mindig[pow(2, 30-i) - 1] == 0:
                    print(-1)
                    break
                else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    file = sys.stdin.readline
    N = int(file())
    A = [None] * N
    mindig = [0 for i in range(30)]
    nim = 0
    for i in range(N):
        a = int(file())
        A[i] = a
        nim ^= a
        reverse = format(a ^ (a - 1), "b").zfill(30)
        for j in range(30):
            if reverse[j] == "1":
                mindig[j] += 1
                break
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if nim[i] == "1":
                if flip % 2 == 0:
                    if mindig[i] == 0:
                        print(-1)
                        break
                    else: flip += 1
            else:
                if flip % 2 == 1:
                    if mindig[i] == 0:
                        print(-1)
                        break
                    else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from functools import reduce
from operator import xor
from sys import exit

def muri():
    print(-1)
    exit()

N = int(input())
A = [int(input()) for _ in range(N)]
X = reduce(xor, A)
T = [False]*33
for a in A:
    T[(a & -a).bit_length()-1] = True

ans = 0

for b in range(32, -1, -1):
    if X & 2**b:
        if not T[b]:
            muri()
        ans += 1
        X ^= 2**(b+1)-1

print(ans)

Submission status: Accepted

Solution code:
from math import log2
n = int(input())
x,y,f,ans,c = [0]*30,[0]*30,1,0,1
for i in range(n):
    a = int(input())
    y[int(log2(a&(-a)))],s = 1,bin(a)[2:][::-1]
    for j in range(len(s)): x[j]+=int(s[j])
for i in range(29,-1,-1):
    if (f and x[i]%2) or (1-f and 1-x[i]%2):
        if y[i]: f,ans = 1-f,ans+1
        else: c = 0
if c: print(ans)
else: print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from functools import reduce
from operator import xor

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=set()
for i, a in enumerate(A):
    bina=format(a, 'b')
    # 2進で最初に1になる桁を、各値について見る
    mnbit.add(len(bina)-bina.rfind('1'))

# 現状のA全部XOR
res=reduce(xor, A, 0)
ln=len(format(res, 'b'))
cnt=0
for i in range(ln):
    idx=ln-i
    # 大きい桁から見て、1になっているところについて処理する
    if res>>(idx-1)&1:
        # その桁用の値があるか
        if idx in mnbit:
            # あればそれを1減らせば、その桁より下が全部反転する(1111..とXORする)
            res^=(1<<idx)-1
            cnt+=1
        else:
            # 必要な桁用の値がなければNG
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from functools import reduce
from operator import xor

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=set()
for i, a in enumerate(A):
    bina=format(a, 'b')
    # 2進で最初に1になる桁を、各値について見る
    mnbit.add(len(bina)-bina.rfind('1'))

# 現状のA全部XOR
res=format(reduce(xor, A, 0), 'b')
cnt=0
ln=len(res)
for i in range(ln):
    idx=ln-i
    # 大きい桁から見て、1になっているところについて処理する
    if res[i]=='1':
        # その桁用の値があるか
        if idx in mnbit:
            # あればそれを1減らせば、その桁より下が全部反転する
            res=format(int(res, 2)^int('1'*idx, 2), '0'+str(ln)+'b')
            cnt+=1
        else:
            # 必要な桁用の値がなければNG
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter
from functools import reduce
from operator import xor

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=[0]*N
for i, a in enumerate(A):
    bina=format(a, 'b')
    mnbit[i]=len(bina)-bina.rfind('1')
C=Counter(mnbit)

res=reduce(xor, A, 0)
ln=len(format(res, 'b'))
cnt=0
for i in range(ln):
    idx=ln-i
    if res>>(idx-1)&1:
        if C[idx]:
            res^=(1<<idx)-1
            cnt+=1
        else:
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter
from functools import reduce
from operator import xor

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=[0]*N
for i, a in enumerate(A):
    bina=format(a, 'b')
    mnbit[i]=len(bina)-bina.rfind('1')
C=Counter(mnbit)

res=format(reduce(xor, A, 0), 'b')
cnt=0
ln=len(res)
for i in range(ln):
    idx=len(res)-i
    if res[i]=='1':
        if C[idx]:
            res=format(int(res, 2)^int('1'*idx, 2), '0'+str(ln)+'b')
            cnt+=1
        else:
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

keta_count = [0] * 65
first_appear = [0] * 65

for a in A:
    i = 0
    while a:
        keta_count[i] += a % 2
        a //= 2
        i += 1

for a in A:
    i = 0
    
    while (a & (1<<(i+1) -1)) != 1<<i:
        i += 1
    first_appear[i] += 1


# print(keta_count)
# print(first_appear)

ans = 0
for i in range(64, -1, -1):
    if keta_count[i] % 2 != 0:

        if first_appear[i] > 0:
            first_appear[i] -= 1
            keta_count[i] -= 1
            ans += 1
            for i in range(0,i):
                keta_count[i] += 1
            # first_appear[0] += 1
        else:
            print(-1)
            exit()

if keta_count[0] % 2 != 0:
    print(-1)
else:
    print(ans)

# print(keta_count)
# print(first_appear)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import xor

N = int(input())
As = [int(input()) for _ in range(N)]

dXORs = set([A ^ (A-1) for A in As])
XOR = reduce(xor, As)

ans = 0
for i in reversed(range(30)):
    if XOR & (1<<i):
        d = ((1<<(i+1)) - 1)
        if d in dXORs:
            XOR ^= d
            ans += 1

print(ans if XOR == 0 else -1)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]


# 全体のxorを計算
XOR = 0
for a in A:
    XOR ^= a


ans = 0
for i in reversed(range(30)):
    if not ((1 << i) & XOR):
        continue

    for j, a in enumerate(A):
        a_bit = bin(a)[2:].zfill(30)
        if a_bit[30 - i - 1:] == '1' + '0' * i:
            ans += 1
            XOR ^= a
            XOR ^= (a - 1)
            del A[j]
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def find_last_one(n: int):
    nbin = bin(n)[2:]
    return 29 - nbin[::-1].index('1')

# 入力
n = ni()
a = [ni() for _ in range(n)]

# aiについて、1のbitともっとも下の1のbit記録
onebit = [0]*30
lastonebit = [0]*30

for ai in a:
    lastonebit[find_last_one(ai)] += 1
    for mask in range(30):
        if ai & (1<<mask):
            onebit[29-mask] += 1

# 上位桁から確定させていく
ans = 0
for digit in range(30):
    if onebit[digit] % 2 == 0:
        continue
    
    elif lastonebit[digit] == 0:
        ans = -1
        break
    
    else:
        ans += 1
        onebit[digit] -= 1
        for d in range(digit+1, 30):
            onebit[d] += 1
            
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
gr = 0
A = []
B = [0]*31
for i in range(N):
  A.append(int(input()))
  B[len(bin(A[i]^(A[i]-1)))-3] += 1
for i in range(N):
  gr ^= A[i]
ans = 0
for i in range(31):
  k = 30 - i
  if gr & (2 ** k):
    if B[k] == 0:
      ans = -1
      break
    else:
      ans += 1
      gr = ~gr
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=0
canuse=[False]*40
for i in range(N):
  A=int(input())
  S^=A
  for k in range(40):
    if A&(1<<k):
      canuse[k]=True
      break
ans=0
for k in range(40)[::-1]:
  if S&(1<<k):
    if canuse[k]:
      S^=(1<<(k+1))-1
      ans+=1
    else:
      print(-1)
      exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())
A=[int(input()) for i in range(N)]
A=sorted(A,reverse=True)
L=[0]*30
M=[0]*30
for a in A:
    s=bin(a)[2:]
    s=s[::-1]
    t=0
    for i in range(len(s)):
        if s[i]=='1':
            L[i]+=1
            if t==0:
                M[i]+=1
                t=1
ans=0
for i in range(29,-1,-1):
    if L[i]%2==1:
        if M[i]==0:
            print(-1)
            sys.exit()
        ans+=1
        if i!=0:
            for j in range(i):
                L[j]+=1
        #print(i,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]

s = 0
L = [False]*44
for a in A:
    s ^= a
    c = 0
    while a&1==0:
        c += 1
        a >>= 1
    L[c] = True
if s==0:
    print(0)
    exit()
ss = "0" + bin(s)[2:]
ans = 0
for i in range(len(ss)-1):
    if ss[-1-i] != ss[-2-i]:
        if L[i]:
            ans += 1
        else:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]

diff = []
XOR = 0
for a in A:
    XOR ^= a
    diff.append(a ^ a-1)

diff.sort(reverse=True)
ans = 0
for d in diff:
    if XOR & ((d + 1) >> 1):
        ans += 1
        XOR ^= d


print(ans if XOR == 0 else -1)

Submission status: Accepted

Solution code:

n = int(input())
a = []
b = 0
for i in range(n):
    x = int(input())
    b ^= x
    a += [x^(x-1)]
ans = 0
a.sort()
for x in a[::-1]:
    if b&((x+1)>>1):
        b^=x
        ans += 1

if b == 0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
xor = lsbsum = 0
for i in range(N):
    n = int(input())
    xor ^= n
    lsbsum |= (n&-n)

ans = 0
while xor > 0:
    msb = 1 << (len(str(bin(xor))) - 3)
    if lsbsum & msb:
        ans += 1
        xor ^= ((msb << 1) - 1)
    else:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
mxlba=0
for i in xrange(n):
    mxlba=max(mxlba,a[i].bit_length())

exist=[False]*(mxlba+5)
for i in xrange(n):
    bit=bin(a[i])[2:]
    lb=len(bit)
    for j in xrange(lb-1,-1,-1):
        if bit[j]=="1":
            exist[lb-1-j]=True
            break

axor=0
for i in xrange(n):
    axor^=a[i]
if axor==0:
    print(0)
    exit()
la=axor.bit_length()
axor=bin(axor)[2:]
ans=0
i=0
while i<la:
    if axor[i]=="1":
        if not exist[la-i-1]:
            print(-1)
            exit()
        else:
            ans+=1
            if la-i-1==0:
                break
            tmp=int("1"*(la-i-1),2)
            axor=int(axor,2)^tmp
            axor=bin(axor)[2:]
    i+=1

print(ans)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
mxlba=0
for i in xrange(n):
    mxlba=max(mxlba,len(bin(a[i])[2:]))

exist=[False]*(mxlba+1000)
for i in xrange(n):
    bit=bin(a[i])[2:]
    lb=len(bit)
    for j in xrange(lb-1,-1,-1):
        if bit[j]=="1":
            exist[lb-1-j]=True
            break

axor=0
for i in xrange(n):
    axor^=a[i]
if axor==0:
    print(0)
    exit()
axor=bin(axor)[2:]
la=len(axor)
ans=0
i=0
while i<la:
    if axor[i]=="1":
        if not exist[la-i-1]:
            print(-1)
            exit()
        else:
            ans+=1
            if la-i-1==0:
                break
            tmp=int("1"*(la-i-1),2)
            axor=int(axor,2)^tmp
            axor=bin(axor)[2:]
    i+=1

print(ans)

Submission status: Accepted

Solution code:
import math as m
import functools


def int_reverse(num):
    num_len = len(bin(num))-2
    f = 2**num_len-1
    return num ^ f

n = int(input())
A = [int(input()) for i in range(n)]
lsbs = [[i for i in range(int(m.log2(a))+1) if (a>>i)&1][0] for a in A]
nim = functools.reduce(lambda x,y:x^y, A)

cnt = 0
for lsb in reversed(sorted(lsbs)):
    if nim == 0:
        break
    if int(m.log2(nim)) == lsb:
        nim = int_reverse(nim)
        cnt += 1

ans = cnt if(nim == 0) else -1
print(ans)

Submission status: Accepted

Solution code:
n = input()
A = [int(raw_input()) for i in xrange(n)]
rest = 0
bits = [0]*32
rbits = [0]*32
for i in xrange(n):
    comm = A[i] & (A[i] - 1)
    rest ^= comm
    bit = (A[i] - comm).bit_length()
    bits[bit] += 1
for i in xrange(32):
    if (rest >> i) & 1:
        rbits[i+1] = 1
ans = 0
for i in xrange(31):
    if rbits[31-i] and not bits[31-i]:
        print -1
        exit(0)
    if (bits[31-i]&1 and not rbits[31-i]) or (bits[31-i]&1==0 and rbits[31-i]):
        ans += 1
        for j in xrange(i, 31):
            rbits[31-j] ^= 1
su = 0
for i in xrange(31):
    su += ((bits[31-i]&1)^rbits[31-i])
print -1 if su else ans

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
read = sys.stdin.read
import numpy as np

n = int(input())
A = np.array(read().split(), dtype=np.int64)
m = 30
C = np.zeros(m, dtype=bool)
used = np.zeros(m, dtype=bool)
x = 0
for a in A:
  x ^= a
for i in range(m):
  idx = np.where(A>>i & 1)
  if np.any(~used[idx]):
    C[i] = True
  used[idx] = True
total = 0
ans = 0
for i in range(m-1, -1, -1):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    m = max(a)
    xor = 0
    for i in a:
        xor ^= i
    i = 1
    cnt = 0
    while True:
        if xor >= i:
            i *= 2
            cnt += 1
        else:
            break
    ans = 0
    for i in range(cnt-1, -1, -1):
        j = (xor & 2**i) // (2**i)
        if j == 1:
            for k in a:
                if k % (2**i) == 0:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1/0)
                return 0
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def solve(n, a):
    """
    References
    ----------
    [1]. 足跡-sokuseki-, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://wk1080id.hatenablog.com/entry/2018/08/17/234023
    [2]. iroiro, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://xxxasdfghjk999.hatenablog.jp/entry/2018/11/01/235259
    [3]. Yang33, 競プロにおけるNim、Grundy数とNimK, http://yang33-kassa.hatenablog.com/entry/2017/12/21/202812
    """
    x = 0
    for i in range(n):
        x ^= a[i]
    b = [a[i] ^ (a[i] - 1) for i in range(n)]
    mapping = {2**k-1: 0 for k in range(30)}
    for y in b:
        mapping[y] += 1
    ans = 0
    for k in range(30, 0, -1):
        y = 2**k - 1
        z = 2**(k-1)
        if (x & z) > 0 and (mapping[y] > 0):
            ans += 1
            mapping[y] -= 1
            x ^= y
    return ans if x == 0 else -1

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))

Submission status: Runtime Error

Solution code:
import math

N=int(input())
A=[int(input()) for _ in range(N)]
#print(A)

B=0
for a in A:
  B^=a

C=[]
D=[0]*30
for a in A:
  C.append(bin(a^(a-1))[2:])
#print(C)
for c in C:
  D[len(c)]=1
#print(D)

ans=0
while B:
  #print(B,bin(B))
  if D[len(bin(B)[2:])]:
    B^=2**len(bin(B)[2:])-1
    ans+=1
  else:
    ans=-1
    break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
xor = 0
rank = [0] * 12 
for i in range(n):
    a = int(input())
    LSB = (a & -a).bit_length()
    rank[LSB] += 1
    xor ^= a 

prev = False 
ans = 0
for i in range(10, -1, -1):
    bit = xor & (1 << i)
    if bit ^ prev:
        if rank[i+1] == 0:
            print(-1)
            exit()
        else:
            ans += 1
    prev = bit
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]

s = 0
L = [False]*22
for a in A:
    s ^= a
    c = 0
    while a&1==0:
        c += 1
        a >>= 1
    L[c] = True
if s==0:
    print(0)
    exit()
ss = "0" + bin(s)[2:]
ans = 0
for i in range(len(ss)-1):
    if ss[-1-i] != ss[-2-i]:
        if L[i]:
            ans += 1
        else:
            print(-1)
            exit()
print(ans)

Submission status: Runtime Error

Solution code:
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
mxlba=0
for i in xrange(n):
    mxlba=max(mxlba,len(bin(a[i])[2:]))
cnt=[0]*(mxlba+5)
for i in xrange(n):
    bit=bin(a[i])[2:]
    lb=len(bit)
    for j in xrange(lb-1,-1,-1):
        if bit[j]=="1":
            cnt[lb-1-j]+=1
            break

axor=0
for i in xrange(n):
    axor^=a[i]
if axor==0:
    print(0)
    exit()
axor=bin(axor)[2:]
la=len(axor)
ans=0
i=-1
while i<la:
    i+=1
    if axor[i]=="1":
        if cnt[i]==0:
            print(-1)
            exit()
        else:
            ans+=1
            cnt[i]-=1
            if la-i-1==0:
                break
            tmp=int("1"*(la-i-1),2)
            axor=int(axor,2)^tmp
            if axor==0:
                break
            axor=bin(axor)[2:]

print(ans)