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

Solution code:
n=(int)(input())
for i in range(n):
  num=(int)(input())
  suuji = list(map(int, input().split(" ")))
  s0=[]
  s1=[]
  ss=input()
  for j in range(num):
    if ss[j] == '1':
      s1.append(suuji[j])
    else:
      s0.append(suuji[j])
  for j in s1:
    if j in s0:
      s1.remove(j)
      s0.remove(j)
  s1=list(set(s1))
  s0=list(set(s0))
  
  for j in s1:
    for k in range(2 ** len(s0)):
      xor = 0
      for l in range(len(s0)):
        if k >> l & 1:
          xor = xor ^ s0[l]
      if j == xor:
        break
    else:
      print(1)
      break
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(i,p):
    if (i,p) in memo:
        return memo[(i,p)]
    if i==N:
        if p==0:
            return 0
        else:
            return 1
    if S[i]=='1':
        res=max(dfs(i+1,p),dfs(i+1,p^A[i]))
    if S[i]=='0':
        res=min(dfs(i+1,p),dfs(i+1,p^A[i]))
    memo[(i,p)]=res
    return res
        

T=int(input())

for _ in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    memo={}
    print(1 if dfs(0,0)>0 else 0)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from typing import List


class Phase:
    def __init__(self, player):
        self.player = player
        self.commmands = []

    def __repr__(self):
        return f"{self.player} with {self.commmands}"


def parse_phases(S, A) -> List[Phase]:
    phases = []
    for i, s in enumerate(S):
        if len(phases) == 0 or phases[-1].player != int(s):
            phases.append(Phase(int(s)))
        phases[-1].commmands.append(A[i])
    return phases


def calc_patterns(x, commmands):
    r = []
    for p in product(*[(False, True) for _ in commmands]):
        y = x
        for i, b in enumerate(p):
            if b:
                y = y ^commmands[i]
        r.append(y)
    return r


def calc_game(S, A):
    x = 0
    phases = parse_phases(S, A)
    for p in phases:
        patterns = calc_patterns(x, p.commmands)
        x = min(patterns) if p.player == 0 else max(patterns)
    return "1" if x > 0 else "0"


if __name__ == "__main__":
    # 整数1個だけ
    T = int(input().strip())
    for _ in range(T):
        N = int(input().strip())
        A = [int(x) for x in input().strip().split(" ")]
        S = input().strip()
        # import pdb; pdb.set_trace()
        print(calc_game(S, A))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import chain, combinations
from functools import reduce


def input():
    return sys.stdin.readline()[:-1]

def xor(a, b):
    return a^b

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = list(map(int, str(input())))
    S1_A = list(set([A[i] for i, x in enumerate(S) if x == 1]))
    S0_A = list(set([A[i] for i, x in enumerate(S) if x == 0]))

    #print(S1_A, S0_A)
    #print(list(powerset(S1_A)))
    
    cand0 = [0]
    cand1 = [0]
    for i in powerset(S1_A):
        if len(i) == 0:
            cand0.append(0)
        else:
            cand1.append(reduce(xor, i))

    for i in powerset(S0_A):
        if len(i) == 0:
            cand0.append(0)
        else:
            cand0.append(reduce(xor, i))

    #print(set(cand1), set(cand0))

    if set(cand0) == set(cand1):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

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

    if s[-1] == "1": # always 1 win
        print(1)
        continue

    mx_a=max(a)

    winset=set([0])
    for i in reversed(range(n)):
        if s[i] == "0":
#            nxt_winset=copy.copy(winset)
            nxt_winset=set()
            for itm in winset:
                nxt_winset.add(itm ^ a[i])
            winset = winset | nxt_winset
        else:
            loseset=set()
            for itm in winset:
                loseset.add(itm ^ a[i])
            winset=loseset

    if 0 in winset:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

for ti in range(t):
  n,a,s = ls[ti]
  z = set()
  o = set()
  for i in range(n):
    if s[i] == "0" and s[i] not in z:
      tmp = set()
      for e in z:
        tmp.add(a[i]^e)
      z = z | tmp
      z.add(a[i])
      #print("z: {}".format(z))
    if s[i] == "1" and s[i] not in o:
      tmp = set()
      for e in o:
        tmp.add(a[i]^e)
      o = o | tmp
      o.add(a[i])
      #print("o: {}".format(o))
  #print(o)
  #print(z)
  #print(o <= z)
  if o<=z:
    print(0)
  else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    t = int(input())

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

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

        que = deque([0])

        for i in range(n):
            tmp = set()
            while que:
                if s[i] == "1":
                    q = que.popleft()
                    if q == 0:
                        tmp.add(q ^ a[i])
                    elif q == a[i]:
                        tmp.add(q)
                    else:
                        tmp.add(q)
                        tmp.add(q ^ a[i])
                else:
                    if a[i] in que or 0 in que:
                        tmp.add(0)
                    else:
                        for q in que:
                            tmp.add(q)
                            tmp.add(q ^ a[i])
                que = deque([])

            for num in tmp:
                que.append(num)

        if 0 in que:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def helper(arr):
    res = set()
    for bit_array in range(1 << len(arr)):
        bit = bit_array
        s = 0
        while bit:
            idx = int(math.log2(bit & ~(bit - 1)))
            s ^= arr[idx]
            bit &= bit - 1
        res.add(s)
    return res


t = int(input())

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

    d = {'0': set(), '1': set()}
    for i in range(n):
        d[s[i]].add(a[i])

    p = helper(list(d['0'])) == helper(list(d['1']))
    print(1 - p)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def solve():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L0 = []
        L1 = []
        for i, v in enumerate(A):
            if S[i] == '0':
                L0.append(v)
            if S[i] == '1':
                L1.append(v)
        sL0 = set(L0)
        sL1 = set(L1)
        for i in range(len(L0))[1:]:
            for v in itertools.combinations(L0, i + 1):
                sL0.add(eval(str(v).replace(', ', '^')))
        for i in range(len(L1))[1:]:
            for v in itertools.combinations(L1, i + 1):
                sL1.add(eval(str(v).replace(', ', '^')))

        # print(N, A, S, L0, L1, sL0, sL1)
        if sL0 == sL1:
            print(0)
        else:
            print(1)


def tmp():
    L0 = [5,6,7]
    sL0 = set(L0)
    L1 = [2,3,4]
    sL1 = set(L1)

    for i in range(len(L0))[1:]:
        for v in itertools.combinations(L0, i+1):
            sL0.add(eval(str(v).replace(', ', '^')))
    for i in range(len(L1))[1:]:
        for v in itertools.combinations(L1, i+1):
            sL1.add(eval(str(v).replace(', ', '^')))
    print(L0,L1)
    print(sL0,sL1)






if __name__ == '__main__':
    solve()
    #tmp()

Submission status: Time Limit Exceeded

Solution code:
import math

def helper(arr):
    res = set()
    for bit_array in range(1 << len(arr)):
        bit = bit_array
        s = 0
        while bit:
            idx = int(math.log2(bit & ~(bit - 1)))
            s ^= arr[idx]
            bit &= bit - 1
        res.add(s)
    return res


t = int(input())

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

    d = {'0': [], '1': []}
    for i in range(n):
        d[s[i]].append(a[i])

    p = helper(d['0']) == helper(d['1'])
    print(1 - p)

Submission status: Time Limit Exceeded

Solution code:
def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)
    return result

T = int(input())
for t in range(T):
    n = input()
    t = input().replace(" ","")
    s = input()
    a0 = [0]
    a1 = [0]
    s = s.rstrip("1")
    for i in range(len(s)):
        if s[i] == "0":
            for j in range(len(a0)):
                a0.append(int(a0[j]) ^ int(t[i]))
        elif s[i] == "1":
            for j in range(len(a1)):
                a1.append(int(a1[j]) ^ int(t[i]))
    if not list_difference(a1,a0):
        print("0")
    else:
        print("1")

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

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

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

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        tmp = set()
        if S[j] == '0':
            for v in win:
                tmp.add(v ^ A[j])
            win |= tmp
        else:
            for v in win:
                if v ^ A[j] not in win:
                    tmp.add(v)
            win -= tmp

    if 0 in win:
        print('0')
    else:
        print('1')

Submission status: Time Limit Exceeded

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

for ti in range(t):
  n,a,s = ls[ti]
  z = set()
  o = set()
  for i in range(n):
    if s[i] == "0":
      tmp = set()
      for e in z:
        tmp.add(a[i]^e)
      z = z | tmp
      z.add(a[i])
      #print("z: {}".format(z))
    if s[i] == "1":
      tmp = set()
      for e in o:
        tmp.add(a[i]^e)
      o = o | tmp
      o.add(a[i])
      #print("o: {}".format(o))
  #print(o)
  #print(z)
  #print(o <= z)
  if o<=z:
    print(0)
  else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
import copy

T = int(input())

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

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

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        tmp = copy.copy(win)
        if S[j] == '0':
            for v in win:
                tmp.add(v ^ A[j])
        else:
            for v in win:
                if v ^ A[j] not in win:
                    tmp.remove(v)

        win = tmp

    if 0 in win:
        print('0')
    else:
        print('1')

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

xor_result = 0

def case(r, n, a, s, index):
  temp = r
  if(n == index):
    return r
  a_case = a[index]
  s_case = s[index]
  index += 1
  
  if(s_case == '1'):
    
    if not ('0' in s[index-1:]):
      return r
    if(r == 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
    else:
      temp = case(r, n, a, s, index)
  elif(s_case == '0'):
    
    if(r != 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
      if(temp != 0):
        temp = case(r, n, a, s, index)
    else:
      if not ('1' in s[index-1:]):
        return r
      temp = case(r, n, a, s, index)
  return temp

for i in range(T):
  N = int(input())
  A = [int(a) for a in input().split()]
  S = input()
  xor_result = case(xor_result, N, A, S, 0)
  if(xor_result == 0):
    print('0')
  else:
    print('1')
  result = 0

Submission status: Time Limit Exceeded

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

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

    if s[-1] == "1": # always 1 win
        print(1)
        continue

    mx_a=max(a)

    winset=set([0])
    for i in reversed(range(n)):
        if s[i] == "0":
            nxt_winset=copy.copy(winset)
            for itm in winset:
                nxt_winset.add(itm ^ a[i])
            winset = nxt_winset
        else:
            loseset=set()
            for itm in winset:
                loseset.add(itm ^ a[i])
            winset=loseset

    if 0 in winset:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
n,a,s = [],[],[]
for i in range(t):
    n.append(int(input()))
    a.append([int(x) for x in input().split(' ')])
    s.append(input())

def ret_set(l, aa):
    sets = {0}
    for j in range(2 ** l):
        buf = [False] * l
        for k in range(l):
            if ((j >> k) & 1):
                buf[l-1-k] = True
        x = 0
        for j in range(l):
            if buf[j]:
                x = x ^ aa[j]
        sets.add(x)
    return sets

for i in range(t):
    if s[i][-1] == '1':
        print(1)
    else:
        l = s[i].rfind('1')+1
        ss = s[i][:l]
        aa = a[i][:l]
        sets = ret_set(l, aa)
        aaa = a[i][l:]
        zeros = ret_set(n[i]-l, aaa)
        if len(sets.difference(zeros)) == 0:
            print(0)
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from functools import reduce
from operator import xor

def checkxor(a,b):
    zero = set()
    for i in range(1,len(a)+1):
        for x in combinations(a,i):
            zero.add(reduce(xor,x))
    for i in range(1,len(b)+1):
        for x in combinations(b,i):
            if reduce(xor,x) not in zero:
                return False
    return True

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1] == '1':
        print('1')
    elif S.count('0') == len(S):
        print('0')
    else:
        zeros = []
        ones = []
        for j in range(len(S)):
            if S[j] == '1':
                ones.append(A[j])
                current = 1
                break
        for k in range(j+1,len(S)):
            if S[k] == '1':
                if current == 1:
                    ones.append(A[k])
                else:
                    if checkxor(zeros,ones) == False:
                        print('1')
                        break
                    else:
                        ones.append(A[k])
                        current = 1
            else:
                if current == 0:
                    zeros.append(A[k])
                else:
                    zeros.append(A[k])
                    current = 0
        if checkxor(zeros,ones) == False:
            print('1')
        else:
            print('0')

Submission status: Time Limit Exceeded

Solution code:
n=(int)(input())
for i in range(n):
  num=(int)(input())
  suuji = list(map(int, input().split(" ")))
  s0=[]
  s1=[]
  ss=input()
  for j in range(num):
    if ss[j] == '1':
      s1.append(suuji[j])
    else:
      s0.append(suuji[j])
  for j in s1:
    for k in range(2 ** len(s0)):
      xor = 0
      for l in range(len(s0)):
        if k >> l & 1:
          xor = xor ^ s0[l]
      if j == xor:
        break
    else:
      print(1)
      break
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def get_bits(n: int) -> Set[int]:
    result = set()
    i = 0
    while n:
        n, r = divmod(n, 2)
        if r:
            result.add(i)
        i += 1
    return result


def solve(values: List[int], _nb: int, s: str) -> bool:
    nbs_0 = set()
    nbs_1 = set()
    for p, n in zip(s, values):
        if p == "0":
            if not nbs_1:
                continue
            next_0 = set(k ^ n for k in nbs_0)
            nbs_0.add(n)
            nbs_0.update(next_0)
            nbs_1.difference_update(nbs_0)
        else:
            next_1 = set(k ^ n for k in nbs_1)
            nbs_1.add(n)
            nbs_1.update(next_1)
            nbs_0 = set()
    # LOG.debug((bits_0, bits_1))
    return not bool(nbs_1)


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    T = int(stdin.readline().strip())
    for _ in range(T):
        N = int(stdin.readline().strip())
        values = list(map(int, stdin.readline().split()))
        S = stdin.readline().strip()
        result = solve(values, N, S)
        print(0 if result else 1, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    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):
    # pylint: disable=super-init-not-called
    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")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

xor_result = 0

def case(r, n, a, s, index):
  temp = r
  if(n == index):
    return r
  a_case = a[index]
  s_case = s[index]
  index += 1
  
  if(s_case == '1'):
    
    if not ('0' in s[index:]):
      return r
    if(r == 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
    else:
      temp = case(r, n, a, s, index)
  elif(s_case == '0'):
    
    if(r != 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
      if(temp != 0):
        temp = case(r, n, a, s, index)
    else:
      if not ('1' in s[index:]):
        return r
      temp = case(r, n, a, s, index)
  return temp

for i in range(T):
  N = int(input())
  A = [int(a) for a in input().split()]
  S = input()
  xor_result = case(xor_result, N, A, S, 0)
  if(xor_result == 0):
    print('0')
  else:
    print('1')
  result = 0

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    t = int(input())

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

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

        que = deque([0])

        for i in range(n):
            tmp = set()
            while que:
                q = que.popleft()
                if s[i] == "1":
                    if q == 0:
                        tmp.add(q ^ a[i])
                    else:
                        tmp.add(q)
                        tmp.add(q ^ a[i])
                else:
                    if q == 0:
                        tmp.add(0)
                    else:
                        tmp.add(q)
                        tmp.add(q ^ a[i])

            for num in tmp:
                que.append(num)

        if 0 in que:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def get_bits(n: int) -> Set[int]:
    result = set()
    i = 0
    while n:
        n, r = divmod(n, 2)
        if r:
            result.add(i)
        i += 1
    return result


def solve(values: List[int], _nb: int, s: str) -> bool:
    nbs_0 = set()
    nbs_1 = set()
    for p, n in zip(s, values):
        if p == "0":
            next_0 = set(k ^ n for k in nbs_0)
            nbs_0.add(n)
            nbs_0.update(next_0)
            nbs_1.difference_update(nbs_0)
        else:
            next_1 = set(k ^ n for k in nbs_1)
            nbs_1.add(n)
            nbs_1.update(next_1)
            nbs_0 = set()
    # LOG.debug((bits_0, bits_1))
    return not bool(nbs_1)


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    T = int(stdin.readline().strip())
    for _ in range(T):
        N = int(stdin.readline().strip())
        values = list(map(int, stdin.readline().split()))
        S = stdin.readline().strip()
        result = solve(values, N, S)
        print(0 if result else 1, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    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):
    # pylint: disable=super-init-not-called
    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")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from functools import reduce
from operator import xor

def checkxor(a,b):
    zero = set()
    one = set()
    for i in range(1,len(a)+1):
        for x in combinations(a,i):
            zero.add(reduce(xor,x))
    for i in range(1,len(b)+1):
        for x in combinations(b,i):
            one.add(reduce(xor,x))
    if zero == one:
        return True
    else:
        return False

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1] == '1':
        print('1')
    elif S.count('0') == len(S):
        print('0')
    else:
        zeros = []
        ones = []
        for j in range(len(S)):
            if S[j] == '1':
                ones.append(A[j])
                current = 1
                break
        for k in range(j+1,len(S)):
            if S[k] == '1':
                if current == 1:
                    ones.append(A[k])
                else:
                    if checkxor(zeros,ones) == False:
                        print('1')
                        break
                    else:
                        ones.append(A[k])
                        current = 1
            else:
                if current == 0:
                    zeros.append(A[k])
                else:
                    zeros.append(A[k])
                    current = 0
        if checkxor(zeros,ones) == False:
            print('1')
        else:
            print('0')