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: Accepted

Solution code:
for _ in range(int(input())):
	n=int(input())
	*a,=map(int,input().split())
	s=input()
	b=[]
	f=0
	for x,c in zip(a[::-1],s[::-1]):
		for y in b:
			x=min(x,x^y)
		if x:
			if c=="1":
				f=1
				break
			b.append(x)
	print(f)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# F2上で基底集合Aにxを追加する
# ex: [[1,0,0],[0,1,0]] + [1,1,1] -> [[1,0,0],[0,1,0],[0,0,1]]
# 各要素は十進数で表記．上の例だと A=[4,2], x=7 -> A=[4,2,1]
def F2_update_basis(A,x):
    for a in A:
        x = min(x,x^a)
    if x:
        A.append(x)
    return A

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        if S[j] == '0':
            d = F2_update_basis(d,A[j])
        else:
            num = len(d)
            d = F2_update_basis(d,A[j])
            if len(d) != num:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 掃き出し法
# ex: [[1,1,0],[1,0,1],[1,1,1]] -> [[1,1,0],[0,1,1],[0,0,1]]
# 行ごとの二進数値で入力する．上の例だと A = [6,5,7] -> g = [6,3,1]
def F2_row_reduction(A):
    n = len(A)
    g = A[:]
    rank = 0
    max_digit = len(format(max(A),'b'))
    for col in range(max_digit)[::-1]:
        pivot = -1
        for row in range(rank,n):
            if g[row]>>col & 1:
                pivot = row
                break
        if pivot == -1: 
            continue
        g[pivot],g[rank] = g[rank],g[pivot]
        for row in range(rank+1,n):
            if g[row]>>col & 1:
                g[row] ^= g[rank]
        rank += 1
    return g

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        rank = 0
        if S[j] == '0':
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                rank += 1
        else:
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# ref https://black-thunder.hatenablog.com/entry/20200610/1591774050

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


t = int(input())
for _ in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    S = input()
    print(solve())

Submission status: Accepted

Solution code:
# 解説AC
# https://black-thunder.hatenablog.com/entry/20200610/1591774050
# 基底の最上位bitの位置はそれぞれ異なる
# https://betrue12.hateblo.jp/entry/2019/03/18/005750

m = (10**18).bit_length()
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = list(map(int, input()))
    base = [0]*m
    for i in reversed(range(n)):
        for j in reversed(range(m)):
            if (1<<j)&a[i]:
                if base[j] == 0:
                    if s[i]:
                        print("1")
                        return
                    else:
                        base[j] = a[i]
                    break
                a[i] ^= base[j]
    print("0")

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

Submission status: Accepted

Solution code:
def gauss_jordan(bs):
    rank = 0
    pivot_cols = []
    for col in reversed(range(61)):
        pivot = -1
        for i,row in enumerate(bs[rank:]):
            if row&(1<<col):
                pivot = rank+i
                break
        if pivot < 0: continue
        pivot_cols.append(col)
        bs[pivot],bs[rank] = bs[rank],bs[pivot]
        for i,row in enumerate(bs):
            if i != rank and row&(1<<col):
                bs[i] ^= bs[rank]
        rank += 1
    return bs

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    bs = []
    for a,s in zip(A[::-1],S[::-1]):
        x = a
        for b in bs:
            x = min(x, x^b)
        if x:
            if s=='0':
                bs.append(x)
                bs = gauss_jordan(bs)
            else:
                return 1
    return 0

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

Submission status: Accepted

Solution code:
T=int(input())

def standardize(x,base_set):
  base_list=sorted(base_set,reverse=True)
  for base in base_list:
    x=min(x,x^base)    
  return x

for _ in range(T):
  N=int(input())
  alist=list(map(int,input().split()))
  slist=list(map(int,input()))
  
  base_set=set()
  for index in reversed(range(N)):
    norm_a=standardize(alist[index],base_set)
    if slist[index]==0:
      base_set.add(norm_a)
    else:
      if norm_a>0:
        print(1)
        break
    #print(index,base_set)
  else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
T = int(input())

def hakidasi(L):
  n = len(bin(max(L))) - 2
  k, end = 0, len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, end):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(end):
      if j == k - 1: continue
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def judge(L, x):
  if L == []:
    return False
  n = len(bin(max(L))) - 2
  m = len(L)
  for i in range(m):
    a = len(bin(x))
    b = len(bin(L[i]))
    if a == b:
      x ^= L[i]
    elif a > b:
      return False
    if x == 0:
      return True
  return False

def main():
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  U = 60
  
  L = []
  for i in range(N - 1, -1, -1):
    if A[i] == 0:
      continue
    n = int(S[i])
    if n == 0:
      L.append(A[i])
      L = hakidasi(L)
      if L[-1] == 0:
        L.pop()
    else:
      m = judge(L, A[i])
      if m == False:
        return 1
  return 0

for i in range(T):
  print(main())

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
def solve():
    base = [] # 基底の初期化
    for a, s in zip(A[::-1], S[::-1]):
        # print(f'a: {a}, s: {s}')
        # for i, y in enumerate(base):
        #     print('base{:d} {:3d}: {:05b}'.format(i, y, y))

       # 従属関係を確認
        x = a
        for y in base:
            x = min(x, x ^ y)

        # A_iがA_{i+1:N}で表現可能ならx=0になっている
        if x:
            if s == "0":
                # print('=>add {:3d}: {:05b}'.format(x, x))
                base.append(x)
            else:
                return 1
    return 0


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

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    base=[]
    for i in range(N-1,-1,-1):
        a=A[i]
        for b in base:
            test=a^b
            if a>test:
                a=test
        if a!=0:
            if S[i]=="1":
                print("1")
                break
            else:
                base.append(a)
    else:
        print("0")

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def gauss_jordan(A, extended=False):
    """ ガウス・ジョルダン法(連立方程式の解) """

    N, M = len(A), max(A).bit_length()
    res = A[:]
    rank = 0
    for col in range(M):
        if extended and col == M-1:
            break
        pivot = -1
        for row in range(rank, N):
            if res[row]>>col & 1:
                pivot = row
                break
        if pivot == -1:
            continue
        res[rank], res[pivot] = res[pivot], res[rank]
        for row in range(N):
            if row != rank and res[row]>>col & 1:
                res[row] ^= res[rank]
        rank += 1
    # 解があるか確認
    for row in range(rank, N):
        if res[row]>>(M-1) & 1:
            return (-1, [])
    return (rank, res)

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()
    M = max(A).bit_length()

    mat = [0] * M
    collen = 1
    for i in range(N-1, -1, -1):
        # 先手番なら今回のA[i]を左辺に取り込む
        if S[i] == '0':
            for k in range(M):
                mat[k] |= (A[i]>>k & 1) << collen
            collen += 1
        # 後手番なら今回のA[i]を右辺として、解があるか確かめる
        else:
            cur = mat[:]
            for k in range(M):
                cur[k] |= (A[i]>>k & 1) << collen
            # これまでの値の集合matでA[i]を作れるかどうか
            rank, res = gauss_jordan(cur, extended=True)
            if rank == -1:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def deepcopy(li): return [x[:] for x in li]

def gauss_jordan(A, extended=False):
    """ ガウス・ジョルダン法(連立方程式の解) """

    N, M = len(A), max(A).bit_length()
    B = A[:]
    rank = 0
    res = []
    for col in range(M):
        if extended and col == M-1:
            break
        pivot = -1
        for row in range(rank, N):
            if B[row]>>col & 1:
                pivot = row
                break
        if pivot == -1:
            continue
        B[rank], B[pivot] = B[pivot], B[rank]
        for row in range(N):
            if row != rank and B[row]>>col & 1:
                B[row] ^= B[rank]
        res.append(col)
        rank += 1
    for row in range(rank, N):
        if B[row]>>(M-1) & 1:
            return (-1, [])
    return (rank, res)

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()
    M = max(A).bit_length()

    mat = [0] * M
    collen = 1
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            for k in range(M):
                mat[k] |= (A[i]>>k & 1) << collen
            collen += 1
        else:
            cur = mat[:]
            for k in range(M):
                cur[k] |= (A[i]>>k & 1) << collen
            rank, res = gauss_jordan(cur, extended=True)
            if rank == -1:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
T = int(input())

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

    list0 = [0] * 64
    ans = 0

    for a, s in zip(reversed(A), reversed(S)):
        while a:
            b = a.bit_length() - 1
            if list0[b]:
                a ^= list0[b]
            else:
                if s == '1':
                    ans = 1
                else:
                    list0[b] = a

                break

        if ans: break

    print(ans)

Submission status: Accepted

Solution code:
T = int(input())

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

    list0 = [0] * 64
    ans = 0

    for a, s in zip(A[::-1], S[::-1]):
        while a:
            b = a.bit_length() - 1
            if list0[b]:
                a ^= list0[b]
            else:
                if s == '1':
                    ans = 1
                else:
                    list0[b] = a

                break

        if ans: break

    print(ans)

Submission status: Accepted

Solution code:
T = int(input())

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

    list0 = [0] * 64

    for a, s in zip(A[::-1], S[::-1]):
        if s == '1':
            while a:
                b = a.bit_length() - 1
                if list0[b]:
                    a ^= list0[b]
                else:
                    break

            if a:
                ans = 1
                break

        else:
            while a:
                b = a.bit_length() - 1
                if list0[b]:
                    a ^= list0[b]
                else:
                    list0[b] = a
                    break

    else:
        ans = 0

    print(ans)

Submission status: Accepted

Solution code:
T = int(input())

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

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

    list0 = [0] * 64

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

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

    else:
        ans = 0

    print(ans)

Submission status: Accepted

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

    ans = 0
    B = []
    for i in range(N)[::-1]:
        a = A[i]
        for b in B:
            a = min(a, a ^ b)
        if a:
            if S[i] == '1':
                ans = 1
                break
            B.append(a)
    print(ans)

Submission status: Accepted

Solution code:
def xor_battle(N, A, S):
    bit = [0] * 64
    # 後ろから、上位のbitから見ていく
    for i in reversed(range(N)):
        Ai, Si = A[i], S[i]
        while Ai:
            n = Ai.bit_length() -1
            if bit[n] == 0 and Si == '1':
                return 1 # 防げないbit
            elif bit[n] == 0 and Si == '0':
                bit[n] = Ai # 防げられるbit
                break
            Ai ^= bit[n]
    return 0

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    T = int(input())

    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()[:-1]
        print(xor_battle(N, A, S))

main()

Submission status: Accepted

Solution code:
T = int(input())

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

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        base = A[j]
        for v in win:
            base = min(base, base ^ v)

        if S[j] == '0':
            win.add(base)
        else:
            if base:
                print('1')
                break
    else:
        print('0')

Submission status: Accepted

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

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = a if a < a ^ b else a ^ b

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

t = I()
for _ in range(t):
    n = I()
    a = LI()
    s = input()
    t = []
    for i, Ai in enumerate(a[::-1]):
        for Ti in t:
            if Ai ^ Ti < Ai: # msb(Ai) >= msb(Ti)
                Ai ^= Ti
        if Ai != 0 and s[n-i-1] == '0':
            t.append(Ai)
        elif Ai != 0 and s[n-i-1] == '1':
            print(1)
            break
    else:
        print(0)

Submission status: Accepted

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

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = a if a < (b := a ^ b) else b

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Submission status: Accepted

Solution code:
T = int(input())

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

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

    list0 = [0] * 64

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

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

    else:
        ans = 0

    print(ans)

Submission status: Accepted

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

    ignore = []

    win = True

    for i in range(N - 1, -1 ,-1):
        startLen = len(ignore)
        #Do Stuff
        curr = A[i]
        for v in ignore:
            if curr ^ v < curr:
                curr = curr ^ v
        if curr != 0:
            ignore.append(curr)
            ignore.sort(reverse = True)
        #End
        endLen = len(ignore)
        if S[i] == '1' and startLen != endLen:
            win = False
            break
            

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

Submission status: Accepted

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

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            B.append(a)

    print(ans)

Submission status: Accepted

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

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            else:
                B.append(a)

    print(ans)

Submission status: Accepted

Solution code:
sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

T = ni()
for _ in range(T):
    N = ni()
    A = [ni() for _ in range(N)]
    S = ns()

    B = []
    ans = 0
    for a, s in zip(reversed(A), reversed(S)):
        for b in B:
            a = min(a, a ^ b)

        if a:
            if s == "1":
                ans = 1
                break
            else:
                B.append(a)

    print(ans)

Submission status: Accepted

Solution code:
class VectorSpace01:
    def __init__(self):
        self.E = []
    
    def chk(self, n):
        for e in self.E:
            n = min(n, n ^ e)
        return 1 if n == 0 else 0
    
    def add(self, n):
        for e in self.E:
            n = min(n, n ^ e)
        if n: self.E.append(n)
        return 1 if n == 0 else 0
    
    def dimension(self):
        return len(self.E)

T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    S = [int(a) for a in input()]
    vs = VectorSpace01()
    for i in range(N)[::-1]:
        a = vs.add(A[i])
        if S[i] and a == 0:
            print(1)
            break
    else:
        print(0)

Submission status: Accepted

Solution code:
def solve():
    dp = [0]
    for a, s in zip(A[::-1], S[::-1]):
        # print(f'a: {a}, s: {s}')
        x = a
        for y in dp:
            # print(f'min({x}, {x ^ y})', end=', ')
            x = min(x, x ^ y)
        # print()
        if s == "0":
            if x:
                dp.append(x)
        else:
            if x:
                return 1
        # print(dp)
    return 0


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

Submission status: Accepted

Solution code:
from collections import Counter
import math
import sys
from bisect import bisect,bisect_left,bisect_right
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def mod(): return 10**9+7
 
for _ in range(INT()):
    n = INT()
    #s = input()
    #n,ma = MAP()
    arr = LIST()
    s = input()
    check = []
    flag = 0
    for i in range(n-1,-1,-1):
        #print(i)
        x = arr[i]
        for j in range(len(check)):
            x = min(x,x^check[j])

        if x == 0:
            continue
        if s[i] == '0':
            check.append(x)
        else:
            print(1)
            flag = 1
            break
    if flag == 0:
        print(0)

Submission status: Accepted

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

t = int(readline())

def get_base(x,basis):
    for b in basis:
        x = min(x,x^b)
    return x

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

    basis = []
    for si,ai in zip(s[::-1], a[::-1]):
        x = get_base(ai,basis)
        if(si=='0')&(x>0):
            basis.append(x)
        elif(si=='1')&(x>0):
            print(1)
            break
    else:
        print(0)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    s = list(input())
    basis = []
    for i in range(n-1, -1, -1):
        for v in basis:
            if a[i] > (a[i] ^ v):
                a[i] = a[i] ^ v
        if a[i] > 0:
            if s[i] == '0':
                basis.append(a[i])
            else:
                return 1
    return 0


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

Submission status: Accepted

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


def main():

    def solve(S, A):
        X = []
        for s, v in zip(S[::-1], A[::-1]):
            for x in X:
                if v & (x & -x):
                    v ^= x
            if v:
                if s == "0":
                    X.append(v)
                else:
                    return 1
        return 0

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():

    # def representable(S, v):
    #     # Sの基底を用いて、vを表現可能か
    #     for s in S:
    #         # sの最下位bitがvにあるなら、xorを加えていく
    #         if v & (s & (-s)):
    #             v ^= s
    #     return v == 0

    # def update(S, v):
    #     # リストSへvを追加する。
    #     for s in S:
    #         # 最下位bitが重複するなら、消しておく
    #         if v & (s & -s):
    #             v ^= s
    #     return S+[v]            # 計算コスト怪しい

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

        # 後ろから見ていく
        # 作成可能な数の集合をあらわす基底を保持していく
        X = []
        for i in reversed(range(N)):
            v = A[i]
            for x in X:
                if v & (x & -x):
                    v ^= x
            if v != 0:
                if S[i] == "0":
                    X.append(v)
                else:
                    lose = True
                    break
        if lose == True:
            print(1)
        else:
            print(0)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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