Problem:


Score : 400 points

Problem Statement

There are two persons, numbered 0 and 1, and a variable x whose initial value is 0.
The two persons now play a game.
The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

Person S_i does one of the following:

Replace x with x \oplus A_i, where \oplus represents bitwise XOR.

Do nothing.

Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

1 \leq T \leq 100

1 \leq N \leq 200

1 \leq A_i \leq 10^{18}

S is a string of length N consisting of 0 and 1.

All numbers in input are integers.

Input

Input is given from Standard Input in the following format.
The first line is as follows:

T

Then, T test cases follow.
Each test case is given in the following format:

N
A_1 A_2 \cdots A_N
S

Output

For each test case, print a line containing 0 if x becomes 0 at the end of the game, and 1 otherwise.

Sample Input 1

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

Sample Output 1

1
0
0

In the first test case, if Person 1 replaces x with 0 \oplus 1=1, we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0.

In the second test case, regardless of the choice of Person 1, Person 0 can make x=0 with a suitable choice.



Sample input:
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000


Sample output:
1
0
0

Submission status: Wrong Answer

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

class BaseXor:
    def __init__(self):
        self.size = 0
        self.base = []
    
    def base_calculate(self, x, b):
        return min(x, x ^ b)

    def make_base(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        return x
    
    def change_base(self, x):
        for i in range(self.size):
            self.base[i] = self.base_calculate(self.base[i], x)
    
    def judge_linearly_dependent(self, x):
        x = self.make_base(x)
        res = True if x else False
        return res
    
    def add_base(self, x):
        judge = self.judge_linearly_dependent(x)
        if judge:
            self.change_base(x)
            self.base.append(x)
            self.size += 1
            return True
        return False

def solve(n, a, s):
    base = BaseXor()
    judge = False
    for i in range(n-1, -1, -1):
        x = s[i]
        if x == "0":
            base.add_base(a[i])
        else:
            judge = base.judge_linearly_dependent(a[i])
            if judge:
                break
    
    res = 1 if judge else 0
    return res

def main():
    t = int(input())
    ans = [0]*t
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        res = solve(n, a, s)
        ans[i] = res
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    #A xor battle
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()

    for i in range(61):
        cur="-1"
        for j in range(N):
            a=A[j]&1
            A[j]>>=1
            if a==1 and s[j]!=cur:
                cur=s[j]
        if cur=="1":
            print(1)
            return
    print(0)




if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc():
        n = int(readline())
        a = list(map(int, readline().split()))
        s = input()
        b = [-1] * 61

        for i in range(n - 1, -1, -1):
            x = a[i]
            if s[i] == "0":
                l = x.bit_length()
                if b[l - 1] == -1:
                    b[l - 1] = x
                else:
                    while b[l - 1] != -1 and x > 0:
                        x ^= b[l - 1]
                        l = x.bit_length()
                    if x != 0:
                        b[l - 1] = x
            else:
                xb = format(x, "b")[::-1]
                l = len(xb)
                cur = 0
                for j in range(l - 1, -1, -1):
                    bit = int(xb[j])
                    cur_bit = int(format(cur,"b").zfill(l)[::-1])
                    if bit ^ cur_bit == 1:
                        if b[j] != -1:
                            cur ^= b[j]
                        else:
                            return print(1)
        return print(0)

    t = int(readline())
    for _ in range(t):
        calc()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,vA,S):
	sZ = {0,}
	for a,c in zip(vA[::-1],S[::-1]):
		v = a
		for z in sZ:
			v = min(v, v^z)
		if c=="0":
			sZ |= {v,}
		elif v not in sZ:
			sZ = set({})
			break
		else:
			pass	# sZ = sZ
		#print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


def main():
	T, = linput()
	for _ in "*"*T:
		N, = linput()
		vA = linput()
		S, = linput(str)
		sol(N, vA, S)

def ran():
	#N = 200
	N=20
	vRan = [random.randint(1,10) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	print(vRan,S)
	sol(N, vRan, S)
	exit(0)
	
if __name__ == "__main__":
	#ran()
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,vA,S):
	sZ = {0,}
	for a,c in zip(vA[::-1],S[::-1]):
		v = a
		for z in sZ:
			v = min(v, v^z)
		if c=="0":
			sZ |= {v,}
		elif v not in sZ:
			sZ = set({})
		else:
			pass	# sZ = sZ
		#print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


def main():
	T, = linput()
	for _ in "*"*T:
		N, = linput()
		vA = linput()
		S, = linput(str)
		sol(N, vA, S)

def ran():
	#N = 200
	N=200
	vRan = [random.randint(1,10**18) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	#print(vRan,S)
	sol(N, vRan, S)
	
if __name__ == "__main__":
	main()
	#ran()

Submission status: Wrong Answer

Solution code:
T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            if b and (a & b) == b:
                a ^= b
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s=input();x=0
    for i in range(n):
        if s[i]=='1':
            if x==0 and a[i]%2==1:x^=1
        else:
            if x==1 and a[i]%2==1:x^=1
    print(x)

Submission status: Wrong Answer

Solution code:
def msb(x):
    cnt = 0
    while x:
        x >>= 1
        cnt += 1
    return cnt


def solve(n, a, s):
    # dp[i] = (i回目時点で最終的に0にできる数の集合)
    dp = [[] for _ in range(n + 1)]
    # dp[n] = [0]
    for i in reversed(range(n)):
        if s[i] == '0':
            x = a[i]
            dp[i] = dp[i + 1].copy()
            dp[i].sort(reverse=True)
            for j in range(len(dp[i])):
                x = min(x, x ^ dp[i][j])
            if x != 0:
                dp[i].append(x)
        else:
            x = a[i]
            dp[i + 1].sort(reverse=True)
            for j in range(len(dp[i + 1])):
                x = min(x, x ^ dp[i + 1][j])
            if x == 0:
                dp[i] = dp[i + 1].copy()
            else:
                dp[i] = []
        # print(i, a[i], s[i], dp[i])
    # print(n, a, s)
    # print(*dp, sep='\n')
    if len(dp[0]) != 0:
        return '0'
    else:
        return '1'


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    ans = solve(n, a, s)
    print(ans)

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s=[int(c) for c in input()]

    if s[-1]==1:
        print(1)

    lastz=0
    while lastz<n and s[-lastz-1]==0:
        lastz+=1
    
    chk=2**(lastz)-1

    for b in range(60):
        current=0
        for i in range(n-lastz):
            if s[i]==1 and (a[i]>>b)&1==1:
                current=1
            if s[i]==0 and current==1 and (a[i]>>b)&1==1:
                current=0
        
        if current==0:
            continue

        for i in range(n-lastz,n):
            if (a[i]>>b)&1==0:
                chk&=~(1<<(i-n+lastz))
    
    if chk>0:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from math import *
from collections import *
from bisect import *
import sys
input=sys.stdin.readline
t=int(input())
while(t):
    t-=1
    n=int(input())
    a=list(map(int,input().split()))
    s=input().rstrip('\n')
    p1,p2=0,0
    for i in range(n):
        if(s[i]=='1'):
            p1=p1|a[i]
        else:
            p2=p2|a[i]
    if(p2==p1):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

def solve(N, A, S):
    dp = [0]

    for i in range(N-1, -1, -1):
        #print(i, dp)
        ai = A[i]

        if S[i] == "0":
            # Pattern 1 -> TLE
            #dp += [x^A[i] for x in dp if x^A[i] not in dp]
            
            # Pattern 2 -> TLE
            #for x in dp:
            #    a = x ^ A[i]
            #    if bisect_left(dp, a) == bisect_right(dp, a):
            #        insort(dp, a)

            #for d in dp:
            #    if ai > ai^d: ai ^= d
            #if ai: dp.append(ai)

            if ai not in dp:
                dp.append(ai)

        if S[i] == "1":
            # Pattern 2 -> TLE
            #if A[i] not in dp:
            #    print("1")
            #    return

            for b in dp:
                if ai > ai^b: ai ^= b

            if ai != 0:
                print("1")
                return

    print("0")

T = n1()
for _ in range(T):
    N = n1()
    A = nn()
    S = s1()
    solve(N, A, S)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

def solve(N, A, S):
    dp = [0]

    for i in range(N-1, -1, -1):
        print(i, dp)
        ai = A[i]
        if S[i] == "0":
            # Pattern 1 -> TLE
            #dp += [x^A[i] for x in dp if x^A[i] not in dp]
            
            # Pattern 2 -> TLE
            #for x in dp:
            #    a = x ^ A[i]
            #    if bisect_left(dp, a) == bisect_right(dp, a):
            #        insort(dp, a)

            for d in dp:
                if ai > ai^d: ai ^= d
            if ai: dp.append(ai)

        if S[i] == "1":
            #if A[i] not in dp:
            #    print("1")
            #    return

            for b in dp:
                if ai > ai^b: ai ^= b

            if ai != 0:
                print("1")
                return

    print("0")

T = n1()
for _ in range(T):
    N = n1()
    A = nn()
    S = s1()
    solve(N, A, S)

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  b=[]
  ans=0
  for i in range(n-1,-1,-1):
    for j in b:
      a[i]=min(a[i],a[i]^j)
    if a[i]!=0:
      if s[i]=="0":
        b.append(a[i])
      else:
        ans=1
  print(ans,a)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
import itertools
T=int(input())

max_digit=60
def conv_bit(n):
  res=[]
  for _ in range(max_digit):
    res.append(n%2)
    n//=2
    
  res.reverse()
  return res

for _ in range(T):
  N=int(input())
  alist=list(map(int,input().split()))
  slist=list(map(int,input()))
  
  # eliminate first 0's turn
  if slist[0]==0:
    for i in range(N):
      if alist[i]==1:
        alist=alist[i:]
        slist=slist[i:]
        break
    else:
      print(0)
      continue  
  #print(slist,alist)
  N=len(alist)
  
  if slist[-1]==1:
    print(1)    
  else:
    bit_list=[[0]*max_digit]
    for index in reversed(range(N)):
      if slist[index]==0:
        bit_list.append(conv_bit(alist[index]))
        
        pivot_set=set()
        for j in range(max_digit):
          pivot_row=-1
          for i in range(len(bit_list)):
            if bit_list[i][j]==1 and not i in pivot_set:
              pivot_row=i
              break
          else:
            continue
          
          for i in range(len(bit_list)):
            if i==pivot_row:
              continue
            if bit_list[i][j]==0:
              continue
            for k in range(j,max_digit):
              bit_list[i][k]^=bit_list[pivot_row][k]
          pivot_set.add(pivot_row)          
        #bit_list.sort(reverse=True)
        #print(index,bit_list)
      else:        
        avec=conv_bit(alist[index])
        #print(index,avec)
        
        contained=True
        for i in range(max_digit):
          if avec[i]==0:
            continue
          for bit in bit_list:
            if bit[i]==1:
              for ii in range(i):
                if bit[ii]==1:
                  break
              else:
                for ii in range(i,max_digit):
                  avec[ii]^=bit[ii]
                break
                
        if sum(avec)>0:
          bit_list=[]            
        #print(index,bit_list)
        
    for bit in bit_list:
      if sum(bit)==0:
        print(0)
        break
    else:
      print(1)

Submission status: Wrong Answer

Solution code:
import itertools
T=int(input())

max_digit=3
def conv_bit(n):
  res=[]
  for _ in range(max_digit):
    res.append(n%2)
    n//=2
    
  res.reverse()
  return res

for _ in range(T):
  N=int(input())
  alist=list(map(int,input().split()))
  slist=list(map(int,input()))
  
  # eliminate first 0's turn
  if slist[0]==0:
    for i in range(N):
      if alist[i]==1:
        alist=alist[i:]
        slist=slist[i:]
        break
    else:
      print(0)
      continue  
  #print(slist,alist)
  N=len(alist)
  
  if slist[-1]==1:
    print(1)    
  else:
    bit_list=[[0]*max_digit]
    for index in reversed(range(N)):
      if slist[index]==0:
        bit_list.append(conv_bit(alist[index]))
        
        pivot_set=set()
        for j in range(max_digit):
          pivot_row=-1
          for i in range(len(bit_list)):
            if bit_list[i][j]==1 and not i in pivot_set:
              pivot_row=i
              break
          else:
            continue
          
          for i in range(len(bit_list)):
            if i==pivot_row:
              continue
            if bit_list[i][j]==0:
              continue
            for k in range(j,max_digit):
              bit_list[i][k]^=bit_list[pivot_row][k]
          pivot_set.add(pivot_row)          
        #bit_list.sort(reverse=True)
        #print(index,bit_list)
      else:        
        avec=conv_bit(alist[index])
        #print(index,avec)
        
        contained=True
        for i in range(max_digit):
          if avec[i]==0:
            continue
          for bit in bit_list:
            if bit[i]==1:
              for ii in range(i):
                if bit[ii]==1:
                  break
              else:
                for ii in range(i,max_digit):
                  avec[ii]^=bit[ii]
                break
                
        if sum(avec)>0:
          bit_list=[]            
        #print(index,bit_list)
        
    for bit in bit_list:
      if sum(bit)==0:
        print(0)
        break
    else:
      print(1)

Submission status: Wrong Answer

Solution code:
#22:21
#解説解答
t = int(input())
scale = 64
scale = 4
double = [2**d for d in range(scale)]
double.reverse()
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    base = [0 for _ in range(scale)]
    for i in range(n)[::-1]:
        now = a[i]
        for d in range(scale):
            if now & double[d]:
                if base[d]:
                    now ^= base[d]
                else:
                    base[d] = now
                    break
        else:
            continue
        if s[i] == '1':
            print(1)
            break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:

t = int(input())
n = []
alist = []
s = []
for i in range(t):
    n.append(int(input()))
    alist.append(input())
    s.append(input())

for ti in range(t):
    xor_number = list(map(int,alist[ti].split()))
    people = list(map(int,list(s[ti])))
    dp = [set()] * (n[ti]+1)
    dp[n[ti]].add(int(0))
    for i in range(n[ti]-1,-1,-1):

        new = xor_number[i]
        reverse_list = list(dp[i+1])
        reverse_list.reverse()
        for j in reverse_list:
            new = min(new, new ^ j )
        if new:
            if people[i] == 0:
                dp[i] = dp[i+1]
                dp[i].add(new)
            else:
                dp[0] = None
                break
        else:
            dp[i] = dp[i+1]

    #make max in one
    if dp[0] == None:
        print(1)
    else: 
        print(0)

Submission status: Wrong Answer

Solution code:
z=0
n=0
s=input()
l=[]
q=""
for i in range(len(s)):
	if s[i]=="0":
		z+=1
		q="0"
	elif s[i]=="1":
		n+=1
		q="1"
	else:
		if z>n:
			n+=1
			q="1"
		elif z<n:
			z+=1
			q="0"
		else:
			if s[i-1]=="1":
				z+=1
				q="0"
			elif s[i-1]=="0":
				n+=1
				q="1"
			else:
				if len(q)!=0:
					if q=="0":
						n+=1
						q="1"
					else:
						z+=1
						q="0"
				else:
					if s.count("1")>s.count("0"):
						z+=1
						q="0"
					else:
						n+=1
						q="1"	
							
	l.append(abs(z-n))
print(max(l))

Submission status: Wrong Answer

Solution code:

t = int(input())
n = []
alist = []
s = []
for i in range(t):
    n.append(int(input()))
    alist.append(input())
    s.append(input())

for ti in range(t):
    xor_number = list(map(int,alist[ti].split()))
    people = list(map(int,list(s[ti])))
    dp = [set()] * (n[ti]+1)
    dp[n[ti]].add(int(0))
    for i in range(n[ti]-1,-1,-1):

        new = xor_number[i]
        reverse_list = list(dp[i+1])
        reverse_list.reverse()
        for j in reverse_list:
            new = min(new, new ^ j )
        if people[i] == 1:
            if (new in dp[i+1]) == True:
                dp[i] = dp[i+1].copy()
            else:
                dp[0] = None
                break
        if people[i] == 0:
            dp[i] = dp[i+1].copy()
            dp[i].add(new)

    #make max in one
    if dp[0] == None:
        print(1)
    else: 
        print(0)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
from math import *
import copy
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def bo(i):
	return ord(i)-ord('a')
from copy import *
from bisect import *	

from itertools import permutations 
def check(p):
	for i in range(n-1,-1,-1):  
		if a[i]&(1<<p):
			if s[i]=='0':
				return 0
			else:
				return 1
	return 0			



t=fi()
while t>0:
	t-=1
	n=fi()
	a=li()
	s=si()
	flag=0
	for j in range(70):
		flag|=check(j)
	print(flag)

Submission status: Wrong Answer

Solution code:
import sys


def main():
    readline = sys.stdin.readline
    T = int(readline())
    for _ in range(T):
        _ = int(readline())
        A = tuple(map(int, readline().split()))
        S = tuple(readline())
        x = 0
        for a, s in zip(A, S):
            b = x ^ a
            if (s == "0" and b < x) or (s == "1" and b > x):
                x = b
        print("0" if x == 0 else "1")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    readline = sys.stdin.readline
    T = int(readline())
    for _ in range(T):
        _ = int(readline())
        A = tuple(map(int, readline().split()))
        S = tuple(readline())
        x = 0
        for a, s in zip(A, S):
            if (s == "0" and a < x) or (s == "1" and a > x):
                x = a
        print("0" if x == 0 else "1")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    readline = sys.stdin.readline
    T = int(readline())
    for _ in range(T):
        N = int(readline())
        A = tuple(map(int, readline().split()))
        S = readline()
        x = 0
        for i in range(N):
            s = S[i]
            a = x ^ A[i]
            if (s == "0" and a < x) or (s == "1" and a > x):
                x = a
        print("0" if x == 0 else "1")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        #print(f'a: {a}, s: {s}')
        #for i, y in enumerate(base):
        #    print('base{:d} {:3d}: {:05b}'.format(i, y, y))
        x = a
        for y in base:
            x = min(x, x ^ y)
        if x:
            if s == "0":
                while x > 0:
                    l = x.bit_length() - 1
                    x_top = x >> l << l
                    #print('=>add {:3d}: {:05b}'.format(x_top, x_top))
                    base.append(x_top)
                    x ^= x_top
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    #print(f'A: {A}, S: {S}')
    print(solve())
    #print('-'*32)

Submission status: Wrong Answer

Solution code:
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        # print(f'a: {a}, s: {s}')
        # for i, y in enumerate(base):
        #     print('base{:d} {:3d}: {:05b}'.format(i, y, y))
        x = a
        for y in base:
            x = min(x, x ^ y)
        if x:
            if s == "0":
                # 最上位bitのみ残す
                l = x.bit_length() - 1
                x = x >> l << l
                # print('=>add {:3d}: {:05b}'.format(x, x))
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    # print(f'A: {A}, S: {S}')
    print(solve())
    # print('-'*32)

Submission status: Wrong Answer

Solution code:
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        x = a
        for y in base:
            x = min(x, x ^ y)
        if s == "0":
            if x:
                base.append(x)
        else:
            if x:
                return 1
    return 0


t = int(input())
for i in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    print('-'*32)

Submission status: Wrong Answer

Solution code:
T = int(input())

for _ in [0]*T:
    N = int(input())
    *A, = map(int,input().split())
    S = input()

    B = []
    ans = 0
    for s,a in zip(S[::-1],A[::-1]):
        if s=="0":
            B.append(a)
        else:
            # check
            C = B[:]
            for i in range(64):
                if (a >> i) & 1 == 0 : continue
                for b in C:
                    if (b >> i) & 1 == 1: break
                else:
                    ans = 1
                    break
                a ^= b
                for j,c in enumerate(C):
                    if (c >> i) & 1 == 1:
                        C[j] = c ^ b
            if ans == 1: break
    print(ans)

Submission status: Wrong Answer

Solution code:
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()

    if S[-1] == '1':
        print(1)
        continue

    list0 = [0] * 64

    for a, s in zip(A[::-1], S[::-1]):
        blen = a.bit_length()
        for i in range(blen, 0, -1):
            if a.bit_length() < i: break
            if list0[i - 1]:
                a ^= list0[i - 1]
                if a == 0: break

        if a:
            if s == '1':
                ans = 1
                break
            else:
                list0[a.bit_length() - 1] = a

    else:
        ans = 0

    print(ans)

Submission status: Wrong Answer

Solution code:
t = int(input())
x = 0
result = []
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    s = input()
    si = [int(i) for i in s]
    l = list(zip(l,s))
    #print(l)
    for key,val in l:
        if val == 1 and x^key != 0:
            x = x^key
        elif val == 0 and x^key == 0:
            x = x^key
        #print(x)
    #print(x)
    result.append(x)
for res in result:
    print(res)

Submission status: Wrong Answer

Solution code:
t = int(input())
x = 0
result = []
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    s = [int(i) for i in input()]
    l = list(zip(l,s))
    #print(l)
    for key,val in l:
        if val == 1 and x^key != 0:
            x = x^key
        elif val == 0 and x^key == 0:
            x = x^key
        #print(x)
    #print(x)
    result.append(x)
for res in result:
    print(res)

Submission status: Wrong Answer

Solution code:
I=input
n=int
for i in range(n(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    t.append(i*(j:=n(j)^1));x|=(i>0)&j
  print(x)

Submission status: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = set()
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if S[-i] == '1':
                print('1')
                break
            else:
                base.add(temp)
    else:
        print('0')