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

def main():
  t = int(input().rstrip())
  
  for i in range(t):
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    s = input().rstrip()
    x = 0
    
    for k in range(n):
      if s[k] == "1" and x ^ int(a[k]) != 0:
        x = x ^ int(a[k])
      if s[k] == "0" and x ^ int(a[k]) == 0:
        x = x ^ int(a[k])
    if x == 0:
      print(0)
    else:
      print(1)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    x = 0
    for i in range(n):
        if(s[i] is '1'):
            if(x ^ a[i] != 0):
                x = x ^ a[i]
        elif(s[i] is '0'):
            if(x ^ a[i] == 0):
                x = x ^ a[i]
    if(x == 0):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import sys 

input = sys.stdin.readline

def main():
  t = int(input().rstrip())
  
  for i in range(t):
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    s = input().rstrip()
    x = 0
    
    for k in range(n):
      if s[k] == "1" and x ^ int(a[k]) != 0:
        x = x ^ int(a[k])
      if s[k] == "0" and x != 0 and x ^ int(a[k]) == 0:
        x = x ^ int(a[k])
    if x == 0:
      print(0)
    else:
      print(1)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:

def solve(N, A, S):
    ret = False
    for i in range(len(A)):
        if S[i] == '1':
            if A[i] % 2 == 1:
                ret = True
        else:
            if A[i] % 2 == 1:
                ret = False
    return ret

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if solve(N, A, S):
        print("1")
    else:
        print("0")

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    INT_BITS = 64
    n = ni()
    a = nl()
    s = ns()
    b = list()
    lis = list()
    for i in range(n):
        if s[i] == '1':
            b.append(a[i])
        else:
            lis.append(a[i])
    idx = 0
    m = len(lis)
    for i in range(INT_BITS-1,-1,-1):
        Mele = -1
        bit_i = 1 << i
        for j in range(idx, m):
            if lis[j] & bit_i and lis[j] > Mele:
                Midx, Mele = j, lis[j]
        if Mele < 0: continue
        lis[Midx], lis[idx] = lis[idx], lis[Midx]
        for j in range(m):
            if j != idx and lis[j] & bit_i:
                lis[j] ^= lis[idx]
        idx += 1
    ans = 0
    for x in b:
        for y in lis:
            if x.bit_length() == y.bit_length():
                x ^= y
                if x == 0:
                    break
        else:
            ans = 1
            break
    print(ans)
    return

T = ni()
for _ in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
	x = 0
	n = int(input())
	a = list(map(int,input().split()))
	s = input()
	for i in range(n):
		mode = int(s[i])
		target = a[i]
		if mode == 0:
			if x == 1 and target == 1:
				x = 0
		else:
			if x == 0 and target == 1:
				x = 1
	print(x)

Submission status: Wrong Answer

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
T = int(input())


def solve(N, A, S):
    w = [0] * 60
    for a, s in zip(A, S):
        b = format(a, "b")[::-1]
        n = len(b)
        for i in range(n):
            if b[i] == "1":
                w[i] = 0 if s == "0" else 1
    if sum(w) == 0:
        return "0"
    else:
        return "1"


def main():
    for _ in range(T):
        # input
        N = int(input())
        A = LI()
        S = input()
        ans = solve(N, A, S)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

for i in range(n):
    a= input()
    if len(a)==1:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    x = 0 
    for i in range(n):
        if s[i] == "0":
            if x == 1:
                if x^a[i] == 0:
                    x = 0
                else:
                    pass
        elif s[i] == "1":
            if x == 0:
                if x^a[i] == 1:
                    x = 1
    print(x)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

def ok(now,a,player):
    if player == "0":
        if now == 0:
            return True
        else:
            if a%2 == 1:
                return True 
            else:
                return False
    else:
        if now == 1:
            return True
        else:
            if a%2 == 1:
                return True
            else:
                return False

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int,(input().split())))
    S = list(input().rstrip())
    n = 0
    for i in range(N):
        if ok(n,A[i],S[i]):
            n = int(S[i])
        else:
            n = (int(S[i])+1)%2
    if n == 0:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
 
 
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1
 
 
def iin(): return int(input())


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


def main():
    T = iin()
    while T:
        T-=1
        n = iin()
        a = lin()
        s = input()
        # a1, a2 = set(), set()
        # for i in range(n):
        #     if s[i] == '0':
        #         a1.add(a[i])
        #     else:
        #         a2.add(a[i])
        # x1 = 0
        # x2 = 0
        # for i in a1:x1 ^= i
        # for i in a2:x2 ^= i
        # print(+ (not x1==x2))
        # print(a1, a2, x1, x2)
        x = 0
        for i in range(n):
            if s[i] == '0':
                if x^a[i] == 0:
                    x ^= a[i]
            else:
                if x^a[i] != 0:
                    x ^= a[i]
        print(+(x!=0))

        

                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout  
  
def main(): 
	N = int(stdin.readline().rstrip())
	for tc in range(N): 
		n = int(stdin.readline().rstrip())
		A = ([int(x) for x in stdin.readline().split()])
		S = stdin.readline().rstrip()
		ans = 0 
		for i in range(n):
			aux = ans ^ A[i]
			if S[i] == '1' and aux != 0:
				ans = aux
			elif S[i] == '0' and aux == 0:
				ans = aux
		if ans != 0:
			ans = 1
		stdout.write(str(ans)+'\n')
		
if __name__ == "__main__": 
	main()

Submission status: Wrong Answer

Solution code:
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


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


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


t = inp()

for _ in range(t):
    n = inp()
    a = inlist()
    s = input()
    x = 0
    for i in range(n):
        person = s[i]
        if person == "0":
            if (x ^ a[i]) == 0:
                x = x ^ a[i]
        elif person == "1":
            if (x ^ a[i]) > 0:
                x = x ^ a[i]

    print(x)

Submission status: Wrong Answer

Solution code:
t=int(input())
for k in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    s=list(str(input()))
    val=0
    for i in range(n):
        if(s[i]=='1'):
            if((val^l[i])!=0):
                val=val^l[i]
        else:
            if((val^l[i])<=0):
                val=val^l[i]
    if(val==0):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout  
  
def main(): 
	N = int(stdin.readline().rstrip())
	for tc in range(N): 
		n = int(stdin.readline().rstrip())
		A = ([int(x) for x in stdin.readline().split()])
		S = stdin.readline().rstrip()
		ans = 0 
		for i in range(n):
			aux = ans ^ A[i]
			if S[i] == '1' and aux != 0:
				ans = aux
			elif S[i] == '0' and aux == 0:
				ans = aux
		stdout.write(str(ans)+'\n')
		
if __name__ == "__main__": 
	main()

Submission status: Wrong Answer

Solution code:
t = int(input())
scale = 64
for _ in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input()
  bit = [[] for _ in range(scale)]
  for x in a:
    for d in range(scale):
      bit[d].append(x%2)
      x //= 2
  rec = []
  for d in range(scale):
    for i in range(n)[::-1]:
      if bit[d][i] == 1:
        rec.append(int(s[i]))
        break
    else:
      rec.append(0)
  if 1 in rec:
    print(1)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
t=int(input())
for z in range(t):
  n=int(input())
  x=0
  a=list(map(int,input().split()))
  s=input()
  for i in range(n):
    if s[i]=="0":
      y=x^a[i]
      if y==0 or y<x:
        x=y
    else:
      y=x^a[i]
      if y!=0 or y>x:
        x=y
  if x==0:
    print(0)
  else:
    print(1)

Submission status: Wrong Answer

Solution code:
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue
 
        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]
 
        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


def compress(string):
    """文字列をランレングス圧縮する
    例) string = "aabccaaabb" -> [(2, a), (1, b), (2, c), (3, a), (2, b)]
    """
    string = string + "#" # 番兵
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans


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

    s = compress(s)
    l = 0
    beki = 0
    for turn, cnt in s:
        tmp = xor_gauss_jordan(a[l:l + cnt])
        l += cnt
        if turn == "1":
            for val in tmp:
                beki |= val
        else:
            for val in tmp:
                beki |= val
                beki -= val
    if beki == 0:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
t = int(input())
scale = 4
for _ in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input()
  bit = [[] for _ in range(scale)]
  for x in a:
    for d in range(scale):
      bit[d].append(x%2)
      x //= 2
  rec = []
  for d in range(scale):
    for i in range(n)[::-1]:
      if bit[d][i] == 1:
        rec.append(int(s[i]))
        break
    else:
      rec.append(0)
  if 1 in rec:
    print(1)
  else:
    print(0)
  #print(bit)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


def popcount(n):
    return bin(n).count("1")


def can_reach_zero(n, bs, s):
    x = 0
    for i, player in enumerate(s):
        b = bs[i]
        cur_count = popcount(x)
        new_count = popcount(x ^ b)
        if player == "0":
            if cur_count >= new_count:
                x ^= b
        else:
            if cur_count <= new_count:
                x ^= b
    return x == 0


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        bs = [int(b) for b in input().split()]
        s = input()
        if can_reach_zero(n, bs, s):
            print(0)
        else:
            print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    ans = '0'
    for n in range(61):
        for i in range(N):
            if S[i]=='1':
                flag = False
                if A[i]&2**n!=0:
                    for j in range(i+1,N):
                        if S[j]=='0':
                            if A[j]&2**n!=0:
                                flag = True
                    if not flag:
                        ans = '1'
    print(ans)

T = int(input())
for t in range(T):
    solve()

Submission status: Wrong Answer

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

    dp = [[0, 0] for i in range(N)]
    # 人１がビットを最後に立てた後に０にできるなら０にならない
    L = max(A).bit_length()

    res = 0
    for i in range(L):
        flag = False
        for j in range(N):
            if (A[j] >> i) % 2 == 1:
                if S[j] == '0':
                    flag = False
                else:
                    flag = True

        if flag:
            res = 1
            break
    print(res)

Submission status: Wrong Answer

Solution code:
for t in range(int(input())):
    n = int(input())
    *a, = map(int,input().split())
    s = input()
    x = 0
    if a[-1]%2==1:
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
t= int(input())
n= int(input())
a= map(int, input().split())
s= int(input())

Submission status: Wrong Answer

Solution code:
t=int(input())
for k in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    s=list(str(input()))
    val=0
    for i in range(n):
        if(s[i]=='1'):
            if((val^l[i])!=0):
                val=val^l[i]
        else:
            if((val^l[i])==0):
                val=val^l[i]
    if(val==0):
        print(0)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
for T in range(int(input())) :
    n = int(input())
    arr= list(map(int,input().split()))
    s = input()

    x = 0
    for i in range(n) :
        if s[i] == '1' :
            if x ==arr[i] :
                continue
            else :
                x = x^arr[i]
        else :
            if x !=0  :
                x  =x^arr[i]

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

Submission status: Wrong Answer

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

def solve(n,A,S):
    d=0
    for a in A:
        d=max(d,a.bit_length())
    for i in range(d):
        for idx in range(n)[::-1]:
            if (A[idx]>>i)&1==1:
                if S[idx]=='1':
                    return 1
                break
    return 0

def main():
    t=int(input())
    for _ in range(t):
        n=int(input())
        A=list(map(int,input().split()))
        S=input().strip()
        ans=solve(n,A,S)
        print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################


for ii in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	#we start with x = 0
	x = 0
	for i in range(n):
		if s[i] == "0":
			if x != 0:
				if x^arr[i] < x:
					x = x^arr[i]
		else:
			if x==0:
				if x^arr[i] != 0:
					x = x^arr[i]
			elif x^arr[i]!=0:
				x = x^arr[i]
		#print(i,x)
	if x == 0:
		print(0)
	else:
		print(1)

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    S = input()

    M = 70
    ans = 0
    for i in range(M):
        for j in range(N-1, -1, -1):
            if S[j] == "1" and A[j] & (1<<i) > 0:
                ans = 1
                break
            elif S[j] == "0" and A[j] & (1<<i) > 0:
                break
        if ans == 1:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
print("I do not know")

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    n = int(input())
    p = [*map(int,input().split())]
    s = input()
    x = 0
    for i in range(n):
        if(s[i]=="1" and x^p[i]!=0):
            x ^= p[i]
        elif (s[i]=="0" and x^p[i]==0):
            x^=p[i]
    print("0" if x==0 else "1")

Submission status: Wrong Answer

Solution code:


T = int(input())

for loop in range(T):

    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    flag = True

    for i in range(64):

        last = None

        for j in range(N):

            if (2**i) & A[j] > 0:
                last = S[j]

        if last == "1":
            print (1)
            flag = False
            break

    if flag:
        print (0)

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    n = int(input())
    p = [*map(int,input().split())]
    s = input()
    x = 0
    for i in range(n):
        if(s[i]=="1"):
            x ^= p[i]
        elif (s[i]=="0" and x!=0):
            x^=p[i]
    print("0" if x==0 else "1")

Submission status: Wrong Answer

Solution code:
print("a")

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  ans=0
  for k in range(18):
    b=[]
    for i in range(n):
      if a[i]&(1<<k):b.append(int(s[i]))
    if 1 in b and b[-1]!=0:ans=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def slv(n,a,s):
    dp=[set(()) for _ in '_'*(n+1)]
    dp[-1]={0}
    for i in range(n-1,-1,-1):
        if s[i]=='0':
            for j in dp[i+1]:
                dp[i].add(a[i]^j)
                dp[i].add(j)
        else:
            if a[i] in dp[i+1]:
                dp[i]=dp[i+1]
            else:
                dp[i]=set(())
            """
            for j in dp[i+1]:
                if a[i]^j in dp[i+1]:
                    dp[i].add(j)
                    dp[i].add(j^a[i])
            """
        if not dp[i]:return 1
    if dp[0]:return 0
    return 1

t=int(input())
n=[]
a=[]
s=[]
for _ in range(t):
    n.append(int(input()))
    a.append(list(map(int,input().split())))
    s.append(input())
for i in range(t):
    print(slv(n[i],a[i],s[i]))

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

1
0
0
"""

Submission status: Time Limit Exceeded

Solution code:
# xor battle

def Normalize(A):
    A.sort(reverse=True)
    start_point = 0
    for i in range(60, -1, -1):
        X = 1 << i
        for j in range(start_point, len(A)):
            if A[j] >> i & 1:
                A[start_point], A[j] = A[j], A[start_point]
                for k in range(len(A)):
                    if A[k] >> i & 1 and k != start_point:
                        A[k] ^= A[start_point]
                start_point += 1
                break

# 最高位のbit を取得

def highest_bit(X):
    cnt = 0
    V = X
    while V & 1 == 0:
        cnt += 1
        V >>= 1
    return cnt


def solve():
    N = int(input())
    a = list(map(int, input().split()))
    player = input()

    p0, p1 = [], []

    for i in range(N):
        if player[i] == "0":
            p0.append(a[i])
        else:
            p1.append(a[i])
    Normalize(p0)
    Normalize(p1)

    for v in p0:
        bit = highest_bit(v)
        for j in range(len(p1)):
            if (v >> bit) & (p1[j] >> bit):
                p1[j] ^= v

    res = 0

    for x in p1:
        res ^= x

    print(res & 1)
    
    return


def main():
    T = int(input())
    for i in range(T):
        solve()
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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]):
		if c=="0":
			sZ |= {a^z for z in sZ}
		elif a 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=8
	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)
	
if __name__ == "__main__":
	main()
	#ran()

Submission status: Time Limit Exceeded

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]):
        if s == '1':
            if a not in dp:
                dp = set()
                break
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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]):
        if s == '1':
            dp = dp if a in dp else set()
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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]):
        if s == '1':
            dp2 = set()
            for b in dp:
                if b ^ a in dp:
                    dp2.add(b)
            dp = dp2
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
for testcase in range(T):
    N=int(input())
    A=[int(i) for i in input().split()]
    S=input()
    DP=[set() for i in range(N+1)]
    DP[N]={0}
    for i in range(N-1,-1,-1):
        if S[i]=="0":
            DP[i]=DP[i+1]|{v^A[i] for v in DP[i+1]}
        else:
            if A[i] in DP[i+1]:
                DP[i]=DP[i+1]
            else:
                DP[i]=set()
    if 0 in DP[0]:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


T = int(input())
for i in range(T):
    n = int(input())
    A = list(map(int, input().split()))
    S = [int(x) for x in input()]
    dp = np.array([0])
    for j in reversed(range(n)):
        if S[j] == 0:
            dp = np.unique(np.append(dp, dp ^ A[j]))
        elif not A[j] in dp:
            print(1)
            break
    else:
        print(0)

Submission status: Time Limit Exceeded

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

def solve(N,A,S):
  #dp[n] = N番目でこうなってたらゼロにできるよリスト
  dp = [set() for _ in range(N+1)]
  dp[n].add(0)
  
  for i in range(N-1,-1,-1):
    if S[i] == '0':
      dp[i] = copy.copy(dp[i+1])
      for v in dp[i+1]:
        dp[i].add(v ^ A[i])
    else:
      if A[i] in dp[i+1]:
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  
  return 0 if 0 in dp[0] else 1


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

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

def solve(N,A,S):
  #dp[n] = N番目でこうなってたらゼロにできるよリスト
  dp = [set() for _ in range(N+1)]
  dp[n].add(0)
  
  for i in range(N-1,-1,-1):
    if S[i] == '0':
      for v in dp[i+1]:
        dp[i].add(v)
        dp[i].add(v ^ A[i])
    else:
      if A[i] in dp[i+1]:
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  
  return 0 if 0 in dp[0] else 1


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

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i+1]:
                dp[i] |= dp[i+1]
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i+1]:
                for v in dp[i+1]:
                    dp[i].add(v)
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def solve(N, A, S):
    dp = set()
    dp.add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            st = set()
            for v in dp:
                st.add(v ^ A[i])
            dp |= st
        else:
            if not A[i] in dp:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = set()
    dp.add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            st = set()
            for v in dp:
                st.add(v ^ A[i])
            dp |= st
        else:
            if not A[i] in dp:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1] == "1":
            ans[i] = 1
        else:
            ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()