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:
#!/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)
    # 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 collections import defaultdict
from functools import lru_cache
itl = lambda: list(map(int, input().strip().split()))


def solve():
    N = int(input())
    nums = itl()
    S = input().strip()
    @lru_cache(None)
    def dp(i, target):
        if i == N:
            return (target == 0)
        if S[i] == '0':
            return dp(i + 1, target ^ nums[i]) or dp(i + 1, target)
        else:
            return dp(i + 1, target ^ nums[i]) and dp(i + 1, target)
    return 0 if dp(0, 0) else 1


T = int(input())
for _ in range(T):
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = map(int, args[i+1].split())
        S = map(int, tuple(args[i+2]))

        A0 = []
        A1 = []
        for a, s in zip(A, S):
            if s == 1:
                A0.append(a)
            elif s == 0:
                A1.append(a)
        X = set([0])
        for a in A1:
            for x in X.copy():
                X.add(a ^ x)

        Y = set([0])
        for a in A0:
            for y in Y.copy():
                Y.add(a ^ y)

        ret.append(1*(1 == len(X & Y)))

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

t = int(input())

for i in range(t):
    n = int(input())
    a = []
    a = list(map(int,input().split()))
    s = input()
    
    if s[len(s)-1] == '1':
#        print("saisyo")
        print(1)
    else:
        
        for i in range(2**len(s)):  # 空集合を除く場合はrange(1, 2**len(list1))
            list2 = []
            x = 0
            if i != 0 and s not in '1':
                # 処理対象の数字を2進数に変換し、各桁のbitが１かどうかを判断する
                for j in range(len(s)):
        	        # 演算結果が1なら処理を行う
                    if (i >> j) &1 == 1 or (s[j] == '1'):
                        if (s[j] == '1') or(s[j] == '0' and x != 0):
                            x = x^a[j]
#                            print(str(i) + ':' + str(x))
                
                if x == 0:
                    break
#        else:
#            print(1)
        if x == 0:
#            print("saigo")
            print(0)
        else:
#            print("saigo")
            print(1)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
from functools import lru_cache
itl = lambda: list(map(int, input().strip().split()))


def solve():
    N = int(input())
    nums = itl()
    S = input().strip()
    @lru_cache(None)
    def dp(i, target):
        if i == N:
            return (target == 0)
        if S[i] == '0':
            return dp(i + 1, target ^ nums[i]) or dp(i + 1, target)
        else:
            return dp(i + 1, target ^ nums[i]) and dp(i + 1, target)
    return 0 if dp(0, 0) else 1


T = int(input())
for _ in range(T):
    print(solve())

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(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:
      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:
#!/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":
            nbs_1.discard(n)
            next_0 = set((n,))
            for k in nbs_0:
                nbs_1.discard(k ^ n)
                next_0.add(k ^ n)
            nbs_0.update(next_0)
        else:
            next_1 = set((n,))
            for k in nbs_1:
                next_1.add(k ^ n)
            nbs_1.update(next_1)
    # 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:
import os

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


DIGIT = (10 ** 18).bit_length()


def solve_f2(mat):
    # 掃き出し法
    rank = 0
    for col in range(mat.shape[1] - 1):
        if rank >= DIGIT:
            break
        row = mat[rank:, col].argmax() + rank
        if not mat[row, col]:
            continue
        pivot = mat[row].copy()
        mat[mat[:, col]] ^= pivot
        mat[row] = mat[rank]
        mat[rank] = pivot
        rank += 1

    if rank < DIGIT and mat[rank:].any():
        # 解無し
        return False
    else:
        return True


def solve(N, A, S):
    if S[-1] == '1':
        return 1

    # すべての1を、それより後ろの0で打ち消せればOK
    S = np.array(list(S), dtype=int) == 1
    A = np.array(A, dtype=int)

    zero_win = True
    # for i in reversed(range(N)):
    #     if S[i]:
    #         a_mat = []
    #         vec = []
    #         for d in reversed(range(DIGIT)):
    #             a_mat.append(A[i + 1:][~S[i + 1:]] >> d & 1)
    #             vec.append([A[i] >> d & 1])
    #         mat = np.hstack((a_mat, vec)).astype(bool)
    #         zero_win &= solve_f2(mat)
    #     if not zero_win:
    #         break
    mat = np.zeros((DIGIT, 0), dtype=bool)
    for i in reversed(range(N)):
        if S[i]:
            vec = []
            for d in reversed(range(DIGIT)):
                vec.append([A[i] >> d & 1])
            zero_win &= solve_f2(np.hstack((mat, vec)).astype(bool))
        else:
            vec = []
            for d in reversed(range(DIGIT)):
                vec.append([A[i] >> d & 1])
            mat = np.hstack((mat, vec)).astype(bool)
        if not zero_win:
            break
    return int(not zero_win)


T = int(sys.stdin.buffer.readline())
for _ in range(T):
    N = int(sys.stdin.buffer.readline())
    A = list(map(int, sys.stdin.buffer.readline().split()))
    S = sys.stdin.buffer.readline().decode().rstrip()
    ans = solve(N, A, S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = []
        while que:
            q = que.popleft()
            if s[i] == "1":
                if q == 0:
                    tmp.append(q ^ a[i])
                else:
                    tmp.append(q)
                    tmp.append(q ^ a[i])
            else:
                if q == 0:
                    tmp.append(0)
                else:
                    tmp.append(q)
                    tmp.append(q ^ a[i])

        for num in tmp:
            que.append(num)

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from functools import lru_cache

def resolve():
    T = int(input())

    @lru_cache
    def f(x, i):
        if i == N:
            return "1" if x else "0"

        ans = f(x, i+1)
        if S[i] == ans:
            return ans
        return f(x^A[i], i+1)

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        if S[-1] == "1":
            ans.append("1")
        else:
            ans.append(f(0, 0))

        f.cache_clear()

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A, S):
    # @lru_cache(maxsize=None)
    def f(i, x):
        # print(' '*i, x)
        if i == N:
            if x == 0:
                return 0
            else:
                return 1
        p = int(S[i])
        if f(i+1, x ^ A[i]) == p:
            return p
        if f(i+1, x) == p:
            return p
        return p ^ 1

    return f(0, 0)


def main():
    T = read_int()
    for _ in range(T):
        N = read_int()
        A = read_int_n()
        S = read_str()
        print(slv(N, A, S))

    # while True:
    #     N = 4
    #     A = [random.randint(1, 1<<4) for _ in range(N)]
    #     S = random.choices('01', k=N-1)
    #     S.append('0')

    #     # A = [2, 9, 6, 15, 7, 6, 9]
    #     # S = ['0', '1', '1', '1', '0', '0', '0']
    #     print(A)
    #     print(S)
    #     r = slv(N, A, S)
    #     print(r)
    #     if r == 0:
    #         break


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:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections,math
sys.setrecursionlimit(1000000)

INF = float("inf")

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
    S = sys.stdin.readline().rstrip()
    def backtrack(i,x):
        if i == N:
            return x==0
        if S[i] == '0':
            if backtrack(i+1,x^int(A[i])) == True or backtrack(i+1,x)==True:
                return True
            else:
                return False
        else:
            if backtrack(i+1,x^int(A[i])) == False or backtrack(i+1,x)==False:
                return False
            else:
                return True

    if backtrack(0,0)==True:
        print("0")
    else:
        print("1")

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 = set([A[i] for i, x in enumerate(S) if x == 1])
    S0_A = set([A[i] for i, x in enumerate(S) if x == 0])

    cand0 = set()
    cand1 = set()
    for i in powerset(S1_A):
        if len(i) == 0:
            cand1.add(0)
        elif len(i) == 1:
            cand1.add(i[0])
        else:
            cand1.add(reduce(xor, i))

    for i in powerset(S0_A):
        if len(i) == 0:
            cand0.add(0)
        elif len(i) == 1:
            cand0.add(i[0])
        else:
            cand0.add(reduce(xor, i))

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

Submission status: Time Limit Exceeded

Solution code:
import os

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


DIGIT = (10 ** 18).bit_length()


def solve_f2(mat):
    # 掃き出し法
    rank = 0
    for col in range(mat.shape[1] - 1):
        if rank >= DIGIT:
            break
        row = mat[rank:, col].argmax() + rank
        if not mat[row, col]:
            continue
        pivot = mat[row].copy()
        mat[mat[:, col]] ^= pivot
        mat[row] = mat[rank]
        mat[rank] = pivot
        rank += 1

    if rank < DIGIT and mat[rank:].any():
        # 解無し
        return False
    else:
        return True


def solve(N, A, S):
    if S[-1] == '1':
        return 1

    # すべての1を、それより後ろの0で打ち消せればOK
    S = np.array(list(S), dtype=int) == 1
    A = np.array(A, dtype=int)

    zero_win = True
    for i in reversed(range(N)):
        if S[i]:
            a_mat = []
            vec = []
            for d in reversed(range(DIGIT)):
                a_mat.append(A[i + 1:][~S[i + 1:]] >> d & 1)
                vec.append([A[i] >> d & 1])
            mat = np.hstack((a_mat, vec)).astype(bool)
            zero_win &= solve_f2(mat)
    return int(not zero_win)


T = int(sys.stdin.buffer.readline())
for _ in range(T):
    N = int(sys.stdin.buffer.readline())
    A = list(map(int, sys.stdin.buffer.readline().split()))
    S = sys.stdin.buffer.readline().decode().rstrip()
    ans = solve(N, A, S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections,math
sys.setrecursionlimit(1000000)

INF = float("inf")

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
    S = sys.stdin.readline().rstrip()
    #print(N,A,S)
    def backtrack(i,x,a):
        if i == N:
            #print(x,a)
            return x==0
        if S[i] == '0':
            if backtrack(i+1,x^int(A[i]),a+[0]) == True or backtrack(i+1,x,a+[1])==True:
                return True
            else:
                return False
        else:
            if backtrack(i+1,x^int(A[i]),a+[0]) == False or backtrack(i+1,x,a+[1])==False:
                return False
            else:
                return True

    if backtrack(0,0,[])==True:
        print("0")
    else:
        print("1")

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 = [A[i] for i, x in enumerate(S) if x == 1]
    S0_A = [A[i] for i, x in enumerate(S) if x == 0]
    #L = [[i for i in  map(int, input().split())] for i in range(T)]

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

    #print(set(cand1))

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

    #print(set(cand0))

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict

T = int(readline())

for _ in range(T):
    N = int(readline())
    A = list(map(int,readline().split()))
    S = readline().rstrip()
    d0 = defaultdict(int)
    d0[0] = 1
    d1 = defaultdict(int)
    d1[0] = 1

    for i,a in enumerate(A):
        d = defaultdict(int)
        if S[i] == '1':
            for k in d1.keys():
                d[k] = 1
                d[k^a] = 1
            d1 = d
        else:
            for k in d0.keys():
                d[k] = 1
                d[k^a] = 1
            d0 = d
    ans = 0
    for k in d1.keys():
        if not d0[k]:
            ans = 1
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
T=int(input())
for i in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    s1={0}
    s0={0}
    for j in range(N):
        if S[j]=="1":
            t1=set()
            for k in s1:
                t1.add(k^A[j])
            s1|=t1
        else:
            t0=set()
            for k in s0:
                t0.add(k^A[j])
            s0|=t0
    for j in s1:
        if j not in s0:
            print(1)
            break
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline

for _ in range(int(input())):
	N = int(input())

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

	@lru_cache(maxsize=None)
	def f(i, v):
		if i == N:
			return v == 0

		if S[i] == '0':
			return f(i+1, v) or f(i+1, v^A[i])
		else:
			if not f(i+1, v) or not f(i+1, v^A[i]):
				return False
			return True

	"""
	good = {0}
	for i in range(N-1, -1, -1):
		ngood = set(good)
		if S[i] == '0':
			for v in good:
				ngood.add(v^A[i])
		else:
			for v in good:
				if (v^A[i]) not in good:
					ngood.remove(v)
		good = ngood
	"""

	print(0 if f(0, 0) else 1)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
for _ in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  if "1" not in s:
    print(0)
    continue
  r=s.rfind("1")
  o=[]
  so=set()
  z=[]
  sz=set()
  for i in range(n):
    if s[i]=="0" and i>r:
      for j in z:
        if a[i]^j not in sz:
          z.append(a[i]^j)
          sz.add(a[i]^j)
      if a[i] not in sz:
        z.append(a[i])
        sz.add(a[i])
    elif s[i]=="1":
      for j in o:
        if a[i]^j not in so:
          o.append(a[i]^j)
          so.add(a[i]^j)
      if a[i] not in so:
        o.append(a[i])
        so.add(a[i])
  if sz<=so:print(0)
  else:print(1)

Submission status: Time Limit Exceeded

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


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))

def solve(N, A, S):
    Now = {0}
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            New = set()
            for s in Now:
                New.add(s)
                New.add(s^a)
            Now = New
        else:
            if not a in Now:
                return False
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, alist, s):
    senkei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if now in senkei:
                pass
            else:
                new=[]
                for sn in senkei:
                    new.append(sn^now)
                senkei+=new
        else:
            if now in senkei:
                pass
            else:
                answer=1
    return answer

t=int(input())
for i in range(t):
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))