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:
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    b=[]
    for i in range(n)[::-1]:
        for e in b:
            a[i]=min(a[i],a[i]^e)
        if a[i]:
            if s[i]=="0":
                b+=[a[i]]
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
#一次独立：rankが成分数
import numpy as np
#0-indexed,MSBがma以下の時
def msb(x,ma=59):
    for i in range(ma,-1,-1):
        if (x>>i)&1:
            return i
    return len()
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    #独立、msb同じものはない
    #逆に異なれば独立
    msbs=[0 for i in range(60)]
    for i in range(n-1,-1,-1):
        now=a[i]
        m=59
        #独立のときfはTrue、独立でない時fはFalse
        while True:
            m=msb(now,m)
            if msbs[m]==0:
                f=True
                break
            now=msbs[m]^now
            if now==0:
                f=False
                break
        if s[i]=="0":
            if f:
                msbs[m]=now
        else:
            if f:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
T=int(input())
for t in range(T):
    N=int(input())
    A=list(map(int,input().split()))[::-1]
    S=input()
    S=[1 if c=='1' else 0 for c in S][::-1]
    l=[]
    r=0
    for i,a in enumerate(A):
        if S[i]:
            for e in sorted(l)[::-1]:
                b=pow(2,e.bit_length()-1)
                if a&b:
                    a^=e
            if a:
                r=1
        else:
            for e in l:
                if a>e^a:
                    a^=e
            if a:
                l.append(a)
    print(r)

Submission status: Accepted

Solution code:
# F_2 ^nの基底クラス
class F2n:
    # LISTを受け取ってbasisを生成する.(掃き出し法)
    def __init__(self,LIST):
        self.basis = []
        for ele in LIST:
            for vec in self.basis:
                ele = min(ele, vec^ele)
            if ele:
                self.basis.append(ele)
    # basisに要素eleを追加できるなら追加しTrueを返す. 追加できないなら何もせず,Falseを返す.
    def Add(self, ele):
        for vec in self.basis:
            ele = min(ele, ele^vec)
        if ele:
            self.basis.append(ele)
            return True
        else:
            return False

def solve():
    n=int(input())
    a=list(map(int,input().split()))[::-1]
    s=input()[::-1]
    h=F2n([])
    for i in range(n):
        if h.Add(a[i]):
            if s[i]=="1":
                print(1)
                return
    print(0)
t=int(input())
for _ in range(t):
    solve()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18

def ddprint(x):
  if DBG:
    print(x)

def cover0(c,d):
    m = len(c)
    for i in range(m):
        if c[i]==0:
            continue
        k = -1
        for j in range(62):
            b = 1<<j
            if c[i]&b != 0:
                k = j
                break
        for j in range(i+1,m):
            if c[j]&b != 0:
                c[j] ^= c[i]
        for j in range(len(d)):
            if d[j]&b != 0:
                d[j] ^= c[i]
    return sum(d)==0

t = inn()
for tt in range(t):
    n = inn()
    a = inl()
    s = ins()
    top = n
    to0 = []
    to1 = []
    done = False
    while top>0:
        prev0 = top
        while top>0 and s[top-1]=='0':
            top -= 1
        top0 = top
        to0.extend(a[top0:prev0])
        prev1 = top
        while top>0 and s[top-1]=='1':
            top -= 1
        top1 = top
        to1.extend(a[top1:prev1])
        cc = [x for x in to0]
        dd = [x for x in to1]
        if not cover0(cc,dd):
            print(1)
            done = True
            break
    if not done:
        print(0)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


t = I()
for _ in range(t):
    n = I()
    A = LI()
    s = S()
    basis = []
    for i in range(n - 1, -1, -1):
        v = A[i]
        for b in basis:
            v = min(v, v ^ b)
        if v:
            if s[i] == '1':
                print(1)
                break
            basis += [v]
    else:
        print(0)

Submission status: Accepted

Solution code:
# 解説AC
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    basis=[]
    for i in range(n-1,-1,-1):
      	# 基底を求める
        for e in basis:
            a[i]=min(a[i],a[i]^e)
        if a[i]:
            if s[i]=="0":
                basis.append(a[i])
            else:
                print(1)
                return
    print(0)

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

Submission status: Accepted

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


def solve():
    N = int(input())
    nums = itl()
    S = input().strip()

    basis = []
    for i in range(N - 1, -1, -1):
        v = nums[i]
        for b in basis:
            v = min(v, v ^ b)
        if v:
            if S[i] == '1':
                return 1
            basis.append(v)
    return 0    


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

Submission status: Accepted

Solution code:
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    check = True
    l = [0]*61
    for i in range(n-1,-1,-1):
        x = a[i]
        for j in range(60,-1,-1):
            if x & (1<<j):
                x ^= l[j]

        if s[i] == "0":
            if x:
                l[x.bit_length()-1] = x
        else:
            if x:
                print(1)
                check = False
                break
    if check:
        print(0)

Submission status: Accepted

Solution code:
def solve(N, A, S):
    
    # s == 0 のa を組み合わせて s==1 の任意のa を張ることができれば0
    # 下から
    
    if int(S[-1]) == 1:
        return 1
    
    B = [None] * max(A).bit_length()
    for i in reversed(range(N)):
        a = A[i]
        s = int(S[i])
        
        if s == 0: #基底生成
            while a:
                l = a.bit_length()-1
                if B[l] == None:
                    B[l] = a
                    break
                a ^= B[l]
        else: # i以上の基底で張れなければ 1
            while a:
                l = a.bit_length()-1
                if B[l] == None:
                    return 1
                a ^= B[l]
    return 0

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

Submission status: Accepted

Solution code:
I=input
n=int
for i in range(int(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:
#!python3

import sys
from functools import reduce
from operator import or_

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

X = 60 # (10**18).bit_length()
def f(a, s, n):
    if s[-1] == "1":
        return 1

    y = bin(reduce(or_, a)).count("1")
    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    y -= 1
                    if y == 0:
                        return 0
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


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

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

        ans.append(f(A, S, N))

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
for i in range(int(input())):
  input()
  t=[]
  for i,j in zip(map(int,input().split()[::-1]),input()[::-1]):
    for k in t:i^=k*(i^k<i)
    if i and j=="0":t.append(i)
    if i and j=="1":print(1);break
  else:print(0)

Submission status: Accepted

Solution code:
#!python3

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

def f(a, s, n):
    if s[-1] == "1":
        return 1

    X = max(a).bit_length()
    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    X -= 1
                    if X == 0:
                        return 0
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


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

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

        ans.append(f(A, S, N))

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

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

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

def f(a, s, n):
    if s[-1] == "1":
        return 1

    B = [None] * X
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    B[x] = ai
                    break
                ai ^= B[x]
        else:
            while True:
                x = ai.bit_length() - 1
                if B[x] == ai: break
                elif B[x] == None:
                    return 1
                ai ^= B[x]
    return 0


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

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

        ans.append(f(A, S, N))

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def solve():
    dp = [[] for _ in range(n+1)]
    dp[n].append(0)
    for i in range(n)[::-1]:
        dp[i] = dp[i+1]
        x = a[i]
        for y in dp[i+1]:
            x = min(x,x^y)
        if s[i] == "0":
            if x:
                dp[i].append(x)
        else:
            if x:
                return 1
    return 0
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    print(solve())

Submission status: Accepted

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):
    Base = []
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            for b in Base:
                a = min(a, a^b)
            if a:
                Base.append(a)
        else:
            for b in Base:
                a = min(a, a^b)
            if a:
                return False
                
    return True

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

Submission status: Accepted

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                update(A[i])
        print(res)


main()

Submission status: Accepted

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        L2 = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                L2 = max(L2, A[i].bit_length())
                update(A[i])
        print(res)
main()

Submission status: Accepted

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L
        ID = A.index(max(A))

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            flag = False
            if x.bit_length() == 60:
                flag = True
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            id = x.bit_length() - 1
            if id >= 0:
                s[id] = x

        res = 0
        L2 = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                L2 = max(L2, A[i].bit_length())
                update(A[i])
        print(res)



main()

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    L = len(Nums)
    index = 0
    bit = dict()
    for i in reversed(range(60)): #掃き出し法
        flag = 0
        tp = (1 << i)
        for j in range(index, L):
            if Nums[j] & tp == tp:
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit[i] = index
                break
        if flag == 1:
            for j in range(L):
                if Nums[j] & tp == tp and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1

    #実際にkを作ることができるか
    ans = 0
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i in bit: ans ^= Nums[bit[i]]
    if ans == k: return True
    else: return False


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

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

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def kitei(SET,b):
  for k in SET:
    if k^b < b:
      b = k^b
  return {b}

def can_made_by(SET,b):
  if SET == set():
    return False
  for k in SET:
    if k^b < b:
      b = k^b
  if b:
    return False
  else:
    return True


def solve():
  N = I()
  A = IL()
  S_ = S()
  
  dp = [None for i in range(N+1)]
  dp[N] = {0}
  for i in range(N)[::-1]:
    if S_[i] == "0":
      if dp[i+1]:
        dp[i] = dp[i+1] | kitei(dp[i+1],A[i])
      else:
        dp[i] = dp[i+1]
    else:
      if can_made_by(dp[i+1],A[i]):
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  if dp[0] == set():
    print(1)
  else:
    print(0)
  
T = I()
for _ in range(T):
  solve()

Submission status: Accepted

Solution code:
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col-1, -1, -1):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return sorted(arr[:rank], reverse=True)

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = []

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a >> b0.bit_length()-1 & 1:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(B0+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
T = int(input())

def check_base(bases, A):
	for n, b in bases:
		if A & (1 << n) != 0:
			A ^= b
	if A == 0:
		return None
	n = 0
	d = 1
	while True:
		if A & d != 0:
			return n, A
		n += 1
		d <<= 1

def append_base(bases, A):
	pair = check_base(bases, A)
	if pair != None:
		bases.append(pair)

def check(N, A_list, S):
	bases = []
	for i in range(N - 1, -1, -1):
		A = A_list[i]
		if S[i] == "0":
			append_base(bases, A)
		else:
			if check_base(bases, A):
				return False
	return True

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

Submission status: Accepted

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

def standard_form(A):
    C = A[:]
    L = 60
    E = []
    ids = []
    for i in range(L):
        e = j0 = None
        mask = (1 << i)-1
        for j, a in enumerate(C):
            if (a >> i) & 1 and (a & mask) == 0:
                e = a
                j0 = j
                break
        else:
            continue
        ids.append(j0)
        for j, a in enumerate(C):
            if j0 == j:
                continue
            if (a >> i) & 1:
                C[j] ^= e
    return [C[e] for e in ids]


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

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(q)
                task = task | set(q)
                task = set(standard_form(list(task)))
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(q)
                q = set(q) | task
                q = set(standard_form(list(q)))
                if task != task | q:
                    win = "1"
                    break

                q = [a[i]]
                now = "0"

    if now == "1":
        q = standard_form(list(q))
        q = set(q) | task
        q = standard_form(list(q))
        q = set(q)
        if task != task | q:
            win = "1"

    print(win)

Submission status: Accepted

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 = tuple(map(int, args[i+1].split()))
        S = tuple(map(int, tuple(args[i+2])))

        ans = False
        dp = [0]*(max(A).bit_length()+1)
        for a, s in reversed(tuple(zip(A, S))):
            m = a.bit_length()
            if s == 0:
                while 0 < a and 0 < dp[m]:
                    a ^= dp[m]
                    m = a.bit_length()
                if 0 < a:
                    dp[m] = a
            elif s == 1:
                while 0 < a:
                    if 0 < dp[m]:
                        a ^= dp[m]
                        m = a.bit_length()
                    else:
                        ans = True
                        break

        ret.append(1*ans)

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 60
def topbit(n):
    res = -1
    for i in range(M,-1,-1):
        if n&2**i!=0:
            res = i
            break
    return res

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    base = {}
    ans = '0'
    for i in range(N-1,-1,-1):
        if S[i]=='0':
            s = A[i]
            while s != 0:
                n = topbit(s)
                if n not in base:
                    base[n] = s
                    break
                else:
                    s ^= base[n]
        else:
            s = A[i]
            while s != 0:
                n = topbit(s)
                if n not in base:
                    ans = '1'
                    break
                else:
                    s ^= base[n]
    print(ans)

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

Submission status: Accepted

Solution code:
from bisect import insort

t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()

    is_ok = 0

    can = []
    for i in range(n - 1, -1, -1):
        a = aaa[i]
        if s[i] == '0':
            for (b, c) in can[::-1]:
                if a & b:
                    a ^= c
            if a:
                b = 1 << (a.bit_length() - 1)
                insort(can, (b, a))
        else:
            for (b, c) in can[::-1]:
                if a & b:
                    a ^= c
            if a:
                is_ok = 1
                break

    buf.append(is_ok)

print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    ans = 0
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(reversed(S)):
        tmp = A[N - 1 - i]
        for l0 in L0:
            if tmp ^ l0 < tmp:
                tmp = tmp ^ l0
        if tmp > 0:
            if s == "1":
                ans = 1
                break
            L0.append(tmp)
    print(ans)

Submission status: Accepted

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


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

    hand = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            # 手持ちでvalを作れるか確認する
            hand.sort(reverse=True)
            for num in hand:
                if val.bit_length() == num.bit_length():
                    val ^= num
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            hand.append(val)
            # 手持ちは基底で管理するので掃き出し法を行う
            hand = xor_gauss_jordan(hand)


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