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: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = True
      break
total = 0
ans = 0
for i in range(m):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
m = 32
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = 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: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = True
total = 0
ans = 0
for i in range(m):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = 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: Wrong Answer

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


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

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

canuse = [True]*N

ans = 0
while w != 0:
    l = w.bit_length()-1
    use = -1
    for i, a in enumerate(A):
        if (1<<l)&a and canuse[i]:
            canuse[i] = False
            use = a
            break
    if use == -1:
        ans = -1
        break
    ans += 1
    w = w ^ use ^ (use-1)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    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) // (2**i) == 1:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1)
                return 0
    print(ans)


main()

Submission status: Wrong Answer

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)
                return 0
    print(ans)


main()

Submission status: Wrong Answer

Solution code:

N = int(input())
lis = []
xor = 0

for i in range(N):

    a = int(input())
    xor ^= a

    now = 0

    while a % (2 ** now) == 0:
        now += 1

    lis.append(now-1)

lis.sort()
lis.reverse()
#print (a,lis)


xornow = 0
while xor <= 2 ** xornow:
    xornow += 1

xornow -= 1
ans = 0

for i in lis:

    if xor == 0:
        break

    if xor ^ (2 ** (i+1) - 1) != xor:
        xor = xor ^ (2 ** (i+1) - 1)
        ans += 1



if xor == 0:
    print (ans)

else:
    print (-1)

Submission status: Wrong Answer

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

A.sort(reverse=True, key=lambda a: (a & -a))

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        while left < N and (A[left] & -A[left]).bit_length() > digit:
            left += 1

        if left >= N or (A[left] & -A[left]).bit_length() != digit:
            print(-1)
            exit()

        ans += 1
        xor ^= ((1 << (digit + 1)) - 1)

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True, key=lambda a: (a & -a))

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        while left < N and (A[left] & -A[left]).bit_length() > digit:
            left += 1

        if left >= N:
            print(-1)
            exit()

        ans += 1
        xor ^= ((1 << (digit + 1)) - 1)

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True, key=lambda a: (a & -a))
D = A[0].bit_length()

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        mask = ((1 << (D + 1)) - 1) ^ ((1 << digit) - 1)
        while left < N and (A[left] & mask) != A[left]:
            left += 1

        if left >= N:
            print(-1)
            exit()

        ans += 1
        xor ^= ((1 << (digit + 1)) - 1)

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
D = A[0].bit_length()

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if xor & (1 << digit) > 0:
        mask = ((1 << (D + 1)) - 1) ^ ((1 << digit) - 1)
        while left < N and (A[left] & mask) != A[left]:
            left += 1

        if left >= N:
            print(-1)
            exit()

        if (A[left] & mask) == A[left]:
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if xor & (1 << digit) > 0:
        while left < N and (A[left] & (1 << digit)) != A[left]:
            left += 1

        if left >= N:
            print(-1)
            exit()

        if (A[left] & (1 << digit)) == A[left]:
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

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

left = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if xor & (1 << digit) > 0:
        while left < N and A[left] != (1 << digit):
            left += 1

        if left >= N:
            print(-1)
            exit()

        if A[left] == (1 << digit):
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

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

left = 0
mask = 0
ans = 0

for digit in range(1, xor.bit_length() + 1)[:: -1]:
    if xor & (1 << digit) > 0:
        while left < N and A[left] > (1 << digit):
            left += 1

        if left >= N:
            print(-1)
            exit()

        if A[left] == (1 << digit):
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

if xor:
    for a in A:
        if a % 2 == 1:
            ans += 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
# cf16-exhibition-final-openA - 1D Matching
def calc(x, y, total):
    MOD = 10 ** 9 + 7
    if y:
        total = (total * y) % MOD
        y -= 1
    else:
        x += 1
    return x, y, total


def main():
    # sort A, B and the lines between A, B shouldn't cross
    # cross <-> not min distance
    N, *AB = map(int, open(0))
    C = sorted([(i, 1) for i in AB[:N]] + [(i, 0) for i in AB[N:]])
    ans, a, b = 1, 0, 0
    for i, t in C:
        if t:  # laptop
            a, b, ans = calc(a, b, ans)
        else:  # power sources
            b, a, ans = calc(b, a, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]-=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: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  n = int(input())
  a = [int(input()) for _ in range(n)]
  nim = 0
  nim2 = 0
  for i in a:
    nim ^= i
    nim2 ^= i-1
  #print(nim,nim2)
  if nim>>n > 0:
    print(-1)
  elif nim > nim2 and nim2 > 0:
    print(-1)
  else:
    if nim == 0:
      print(0)
    else:
      ans = 1
      while nim >= 1:
        ans += nim%2
        nim = nim>>2
      print(ans)

solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  n = int(input())
  a = [int(input()) for _ in range(n)]
  nim = 0
  for i in a:
    nim ^= i
  if nim>>n > 0:
    print(-1)
  else:
    if nim == 0:
      print(0)
    else:
      ans = 1
      while nim >= 1:
        ans += nim%2
        nim = nim>>2
      print(ans)

solve()

Submission status: Wrong Answer

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 ^ prev:
        if rank[i+1] == 0:
            print(-1)
            exit()
        else:
            ans += 1
    prev = bit
print(ans)

Submission status: Wrong Answer

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)
    x = reduce(xor, A)
    ans = 0
    for i in range(N):
        if x:
            x ^= A[i] ^ (A[i] - 1)
            ans += 1
        else:
            break
    print(ans if x == 0 else -1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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(set(B))[::-1]:
	while k and not(x&k):
		k//=2
	if b&k:
		x^=b
		z+=1
print(-1if x else z)

Submission status: Wrong Answer

Solution code:
N,*A=map(int,open(0))
x=0
B=[]
for a in A:
	x^=a
	B+=a^a-1,
z=0
for b in sorted(set(B))[::-1]:
	if x&b:
		x^=b
		z+=1
print(-1if x else z)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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
			ans += 1
	else:
		gr %= (1<<(i+1))
if ok:
	print(ans)
else:
	print(-1)

Submission status: Wrong Answer

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(31, -1, -1):
	if (gr>>i)&1:
		if i not in exist:
			ok = False
		else:
			gr %= (1<<(i+1))
			gr = (1<<(i+1)) - gr
			ans += 1
if ok:
	print(ans)
else:
	print(-1)

Submission status: Wrong Answer

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(31, -1, -1):
	if (gr>>i)&1:
		if i not in exist:
			ok = False
		else:
			gr %= (1<<i)
			gr = (1<<i) - gr
			ans += 1
if ok:
	print(ans)
else:
	print(-1)

Submission status: Wrong Answer

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]*30
for i in range(1,30):
    two[i]=two[i-1]*2
ans=0
for i in range(29,0,-1):
    if ans<0:
        break
    if x%two[i]//two[i-1]==1:
        if cnt[two[i]-1]>0:
            cnt[two[i]-1]-=1
            ans+=1
            x^=two[i]-1
        else:
            ans=-1
            break
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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)
            A[j] -= 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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):
        if a == 2 ** i:
            ans += 1
            XOR ^= a
            XOR ^= (a - 1)
            A[j] -= 1
            break
    else:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

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

diff = set()
XOR = 0
for a in A:
    XOR ^= a
    diff.add(a ^ a-1)

ans = 0
for k in range(29)[::-1]:
    if XOR & (1 << k) and 2**(k+1)-1 in diff:
        ans += 1
        XOR = XOR ^((2 ** (k+1)) - 1)

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

Submission status: Wrong Answer

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

LSB = set()
XOR = 0
for a in A:
    XOR ^= a
    LSB.add(int(log((a ^ (a-1)) + 1, 2)))

ans = 0
for k in range(29)[::-1]:
    if XOR & (1 << k) and (k+1) in LSB:
        ans += 1
        XOR = XOR ^((2 ** (k+1)) - 1)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = sorted([int(input()) for i in range(N)], reverse=True)
LSB = [0] * 30
XOR = np.array([0] * 30)

for a in A:
    bit = list(map(int, list(bin(a)[2:])[::-1]))
    for i in range(len(bit)):
        if bit[i] == 1:
            LSB[i] += 1
            break
            
    bit = np.array(bit)
    bit = np.pad(bit, (0, 30 - len(bit)), mode='constant')
    XOR += bit

ans = 0
for i in range(4)[::-1]:
    if XOR[i] % 2 == 1:
        if LSB[i] > 0:
            ans += 1
            LSB[i] -= 1
            XOR[:i] += 1
        else:
            print(-1)
            break
else:
    print(ans)

Submission status: Wrong Answer

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

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 mxlba-i-1==0:
                break
            tmp=int("1"*(mxlba-i-1),2)
            axor=int(axor,2)^tmp
            axor=bin(axor)[2:]

print(ans)

Submission status: Wrong Answer

Solution code:
import math
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)]
nim = functools.reduce(lambda x,y:x^y, A)

cnt = 0
for a in reversed(sorted(A)):
    if int(math.log2(nim)) == int(math.log2(a)) or nim == 1:
        nim = int_reverse(nim)
        cnt += 1

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

Submission status: Wrong Answer

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] and not rbits[31-i]:
        ans += 1
        for j in xrange(i, 31):
            rbits[31-j] ^= 1
su = 0
for i in xrange(31):
    su += (bool(bits[31-i])^rbits[31-i])
print -1 if su else ans

Submission status: Wrong Answer

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] and not rbits[31-i]:
        ans += 1
        for j in xrange(i+1, 31):
            rbits[31-j] ^= 1
        bits[31-i] = 0
su = 0
for i in xrange(31):
    su += (bits[31-i]^rbits[31-i])
print -1 if su else ans

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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(set(B))[::-1]:
	while not(x&k):
		k//=2
	if b&k:
		x^=b
		z+=1
print(-1if x else z)

Submission status: Accepted

Solution code:
import math

n = int(input())
x = 0
s = [0] * 35
for _ in range(n):
    a = int(input())
    x ^= a
    s[int(math.log2(int((a ^ (a - 1)) + 1))) - 1] = 1
t = [0] * 35
while True:
    if x == 0:
        break
    y = int(math.log2(x))
    t[y] = 1
    x -= pow(2, y)
s.reverse()
t.reverse()
ans = 0
now = 0
for i in range(35):
    if now == t[i]:
        continue
    else:
        if s[i] == 1:
            ans += 1
            now = 1 - now
        else:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
xora = 0
xorls = []
for i in a:
  xora ^= i
  xorls.append(i^(i-1))
xorls.sort(reverse=True)
ans = 0
for i in xorls:
  if xora == 0:
    break
  if xora.bit_length() == i.bit_length():
    xora ^= i
    ans += 1
if xora:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
for i in range(N): a[i] = int(input())
table = [0] * N
for i in range(N):
  x = a[i]
  bn = list(bin(x)[2: ])
  bn.reverse()
  for j in range(len(bn)):
    if bn[j] == "1":
      table[i] = (1 << j) - 1 + (1 << j)
      break
#print(table)
xm = 0
for x in a: xm ^= x
table.sort(reverse = True)
res = 0
for x in table:
  if xm ^ x < xm:
    res += 1
    xm ^= x
if xm: print(-1)
else: print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
s = set()
x = 0
for i in range(n):
    x ^= a[i]
    s.add(len(bin(a[i] & -a[i])) - 3)
res = 0
for i in range(50, -1, -1):
    if (x >> i) & 1:
        if i in s:
            x ^= (1 << (i + 1)) - 1
            res += 1
        else:
            print(-1)
            exit(0)
print(res)

Submission status: Accepted

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(n, 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: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = True
      break
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: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
ALL=0
bit=[0 for i in range(31)]

for i in range(N):
    a=int(input())
    ALL^=a
    B=100
    for j in range(31):
        if a//(2**(30-j))==1:
            B=j
        a%=(2**(30-j))
    bit[B]=1
#print(bit)
all=[0 for i in range(31)]
for j in range(31):
    if ALL//(2**(30-j))==1:
        all[j]+=1
    ALL%=(2**(30-j))
#print(all)
cnt=0
ans=0
for i in range(31):
    if (all[i]+cnt)%2==1:
        if bit[i]>=1:
            ans+=1
            cnt+=1
        else:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]

ans = 0
for i in range(n):
    ans ^= a[i]

set_ = set()
for i in range(n):
    set_.add(a[i] ^ (a[i] - 1))
 
cnt = 0
for i in range(50)[::-1]:
    if ans & (1 << i):
        cnt += 1
        if (1 << (i + 1)) - 1 in set_:
            ans ^= (1 << (i + 1)) - 1
        else:
            print(-1)
            exit()
print(cnt)

Submission status: Accepted

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


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

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

canuse = [True]*N

ans = 0
while w != 0:
    l = w.bit_length()-1
    use = -1
    for i, a in enumerate(A):
        if (1<<l)&a and canuse[i] and not (1<<l)&(a-1):
            canuse[i] = False
            use = a
            break
    if use == -1:
        ans = -1
        break
    ans += 1
    w = w ^ use ^ (use-1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
t = 0
for x in a: t ^= x
s = set((x&-x).bit_length() for x in a)
cnt = 0
while t:
  if t.bit_length() in s:
    cnt += 1
    t ^= (1 << t.bit_length()) - 1
  else:
    print(-1)
    break
else: print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    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) // (2**i) == 1 and k % (2**i) == 0:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1)
                return 0
    print(ans)


main()

Submission status: Accepted

Solution code:

N = int(input())
lis = []
xor = 0

for i in range(N):

    a = int(input())
    xor ^= a

    now = 0

    while a % (2 ** now) == 0:
        now += 1

    lis.append(now-1)

lis.sort()
lis.reverse()
#print (a,lis)

ans = 0

for i in lis:

    if xor == 0:
        break

    if xor >= (2 ** i) and xor ^ (2 ** (i+1) - 1) != xor:
        xor = xor ^ (2 ** (i+1) - 1)
        ans += 1



if xor == 0:
    print (ans)

else:
    print (-1)

Submission status: Accepted

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

digits = set()

for a in A:
    digits.add((a & -a).bit_length() - 1)

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

ans = 0

for digit in range(xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        if digit in digits:
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

print(ans)

Submission status: Accepted

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

A.sort(reverse=True, key=lambda a: (a & -a))

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

left = 0
ans = 0

for digit in range(xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        while left < N and ((A[left] & -A[left]).bit_length() - 1) > digit:
            left += 1

        if left >= N or ((A[left] & -A[left]).bit_length() - 1) != digit:
            print(-1)
            exit()

        ans += 1
        xor ^= ((1 << (digit + 1)) - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return(int(sys.stdin.readline()))
def IR(n): return([I() for _ in range(n)])

def main():
    N = I()
    A = IR(N)

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

    dic = {}
    for a in A:
        dic[a^(a-1)] = True
    
    ans = 0
    while(x!=0):
        y=0
        while ((1<<(y+1))<=x):
            y+=1
        if dic.get((1<<(y+1))-1,False):
            x^=((1<<(y+1))-1)
            ans += 1
        else:
            return(-1)
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

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(31)}
    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: Accepted

Solution code:
from collections import defaultdict

#入力、初期化
N = int(input())
D1 = defaultdict(int)
D2 = defaultdict(int)
A = 0
for i in range(N):
	a = int(input())
	A = A ^ a
	D1[a ^ (a - 1)] += 1

#計算
n = A.bit_length()
for i in range(n):
	if A >= 2 ** (n - i - 1):
		D2[2 ** (n - i) - 1] += 1
		A = A ^ (2 ** (n - i) - 1)

#判定
judge = "Yes"
for i in D2:
	if D2[i] > D1[i]:
		judge = "No"
		break
#出力
if judge == "No":
	print(-1)
else:
	print(len(D2))