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:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=60#60桁まで
    
    #S=1となる全ての数字が，それより後ろのS=0のもので構成できれば良い（それらを組み合わせても，S=0側も同じ組み合わせ方で対応できる）．
    #S=0のものを基底ベクトル(ぽいもの)として持っておく
    #このとき行列の標準形を構成するベクトルをイメージ
    #上位桁が等しいものがある場合，それとxorしておけば良い，これによって上位桁が同じ基底ベクトル(ぽいもの)がなくなる
    
    
    def pipo(x):
        #最上位桁が何処か
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        #後ろから見ていき，S=1の時に「S=0の数だけで作れない数」が出てきたらNG
        Vec=[]#基底管理
        flag=1#ダメなら0になる
        for i in range(N-1,-1,-1):
            #print(i,S[i]) 
            if S[i]=="0":

                now=A[i]
                p=pipo(A[i])
                for v in Vec:
                    if v[1]==p:
                        now=now^v[0]
                        p=pipo(now)
                if now!=0:
                    Vec.append((now,pipo(now)))
                    Vec.sort(reverse=True)
                            
                
            else:
                #print(Vec)
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Submission status: Accepted

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

    for i in range(N-1, -1, -1):
        ai = A[i]
        if ai==0:
            continue
        top = ai.bit_length() - 1

        #assert ai & 1<<top
        for j in range(i-1, -1, -1):
            if A[j] >> top & 1:
                A[j] ^= ai
    #print(A,S)
    for a, c in zip(A[::-1], S[::-1]):
        if c==1 and a:
            break
    else:
        print("0")
        continue
    print("1")

Submission status: Accepted

Solution code:
class VectorSpace:
    def __init__(self, k):
        self.k = k
        self.E = [0] * k
    
    def chk(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        return 1 if n == 0 else 0
    
    def add(self, n):
        for i in range(self.k)[::-1]:
            n = min(n, n ^ self.E[i])
        if n: self.E[n.bit_length() - 1] = 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 = VectorSpace(60)
    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(n, a_list, s):

    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            if a_list[i] == 0:
                continue
            r = 2 ** (a_list[i].bit_length() - 1)
            for j in range(i):
                if a_list[j] & r > 0:
                    a_list[j] = a_list[i] ^ a_list[j]
        else:
            if a_list[i] > 0:
                return 1
    return 0


def main():
    t = int(input())
    res_list = []
    for _ in range(t):
        n = int(input())
        a_list = list(map(int, input().split()))
        s = input()
        res = solve(n, a_list, s)
        res_list.append(res)
    for res in res_list:
        print(res)


def test():
    assert solve(2, [1, 2], "10") == 1
    assert solve(2, [1, 1], "10") == 0
    assert solve(6, [2, 3, 4, 5, 6, 7], "111000") == 0


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            while a:
                n = a.bit_length() - 1
                if B[n] == 0:
                    return 1
                a ^= B[n]
        else:
            while a:
                n = a.bit_length() - 1
                if B[n] == 0:
                    B[n] = a
                    break
                a ^= B[n]
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=60
    


    
    def pipo(x):
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        #後ろから見ていき，S=0の数だけで作れない数が(S=1の時に)出てきたらNG
        Vec=[]
        flag=1
        for i in range(N-1,-1,-1):
            #print(i,S[i]) 
            if S[i]=="0":
                if Vec==[]:
                    Vec.append((A[i],pipo(A[i])))
                else:
                    now=A[i]
                    p=pipo(A[i])
                    for v in Vec:
                        if v[1]==p:
                            now=now^v[0]
                            p=pipo(now)
                    if now!=0:
                        Vec.append((now,pipo(now)))
                        Vec.sort(reverse=True)
                            
                
            else:
                #print(Vec)
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(item) for item in input().split()]
    s = input().rstrip()
    if s[-1] == "1":
        print(1)
        continue
    group = []
    prev = "-1"
    for ch, num in zip(s, a):
        if prev != ch:
            group.append([])
        group[-1].append(num)
        prev = ch
    group.reverse()
    tools = []
    ok = True
    for itr, g in enumerate(group):
        if itr % 2 == 0:
            for item in g:
                tools.append(item)
        else:
            tl = tools[:]
            index = 0
            for i in range(64, -1, -1):
                flag = 0
                for j in range(index, len(tl)):
                    if tl[j] & (1 << i):
                        flag = 1
                        tl[index], tl[j] = tl[j], tl[index]
                        break
                for j in range(index + 1, len(tl)):
                    if tl[j] & 1 << i:
                        tl[j] ^= tl[index]
                if flag == 1:
                    index += 1
            for item in g:
                current = 0
                for val in tl:
                    index = len(bin(val)) - 3
                    if item >> index != current >> index:
                        current ^= val
                if current != item:
                    ok = False
    if ok:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    ans = '0'
    for i in range(N):
        if S[i]=='1':
            l = []
            for j in range(i+1,N):
                if S[j]=='0':
                    l.append(A[j])
            for k in range(len(l)):
                l.sort()
                for j in range(len(l)-1):
                    if l[j+1]^l[j] < l[j+1]:
                        l[j+1],l[j] = l[j],l[j+1]^l[j]
                
            s = A[i]
            for j in range(len(l)-1,-1,-1):
                if s^l[j] < s:
                    s ^= l[j]
            if s != 0:
                ans = '1'
    print(ans)
def main():
    T = int(input())
    for t in range(T):
        solve()

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def matmul(a, b, mod):
    m = len(a)
    l = len(a[0])
    n = len(b[0])
    ret = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            e = 0
            for k in range(l):
                e = (e + a[i][k] * b[k][j]) % 2
            ret[i][j] = e
    return ret

def calc(X, v, r):
    rr = 0
    for i in range(r, D):
        if v[i][0] == 1:
            rr = i
            break
    v[rr], v[r] = v[r], v[rr]
    X[rr], X[r] = X[r], X[rr]
    for i in range(D):
        if i == r or v[i][0] == 0:
            continue
        for c in range(D):
            X[i][c] = (X[i][c] + X[r][c]) % 2

T = int(input())
D = 64
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    X = [[int(i == j) for j in range(D)] for i in range(D)]
    r = 0
    for i in range(N)[::-1]:
        v = [[A[i] >> j & 1] for j in range(D)]
        if S[i] == '0':
            v = matmul(X, v, 2)
            if any(v[j][0] == 1 for j in range(r, D)):
                calc(X, v, r)
                r += 1
        else:
            v = matmul(X, v, 2)
            if any(v[j][0] == 1 for j in range(r, D)):
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def judge(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i not in pivot:
        return False
      for j in range(cnt,len(mat)):
        if mat[j]&1<<i:
          x ^= mat[j]
          cnt = j+1
          break
  if x == 0:
    return True
  else:
    return False
def add(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i in pivot:
        for j in range(cnt,len(mat)):
          if mat[j]&1<<i:
            x ^= mat[j]
            cnt = j+1
            break
      else:
        pivot.add(i)
        for j in range(len(mat)):
          if mat[j] < x:
            mat.insert(j,x)
            for k in range(i)[::-1]:
              if mat[j]&1<<k and k in pivot:
                for l in range(j+1,len(mat)):
                  if mat[l]&1<<k:
                    mat[j] ^= mat[l]
            x = mat[j]
            break
        else:
          mat.append(x)
        for j in range(len(mat)):
          if mat[j] > x and mat[j]&1<<i:
            mat[j] ^= x
        break
t = int(input())
for _ in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input().rstrip()
  pivot = set()
  mat = []
  for i in range(n)[::-1]:

    x = a[i]
    if s[i] == "0":
      if judge(mat,x,pivot):
        continue
      else:
        add(mat,x,pivot)
    else:
      if judge(mat,x,pivot):
        continue
      else:
        print(1)
        break
  else:
    print(0)

Submission status: Accepted

Solution code:
def kosu(kitei, aaa, tuika):
    global now_ret
    ret = 0
    n=len(kitei)
    ret2=0
    kitei.append(aaa)
    n+=1
    for i in range(n):
        if kitei[i]:
            ret2 += 1
            x = 0
            while (2**(x+1)) <= kitei[i]:
                x += 1
            for y in range(i+1, n, 1):
                if kitei[y] & (2 ** x):
                    kitei[y] ^= kitei[i]
    
    if now_ret==ret2:
        return 1
    else:
        if tuika==1:
            now_ret+=1
        return 0
 
 
def solve(n, alist, s):
    kitei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if kosu(kitei, now, 1)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer
 
t=int(input())
for i in range(t):
    now_ret=0
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))

Submission status: Accepted

Solution code:
T = int(input())

for _ in range(T):
    N = int(input())
    As = list(map(int, input().split()))
    S = list(input())
    mine = [0] * 61
    for a, s in reversed(list(zip(As, S))):
        bl = a.bit_length()
        if s == '0':
            while bl > 0:
                if (a >> (bl-1)) & 1:
                    if mine[bl] == 0:
                        mine[bl] = a
                        break
                    a ^= mine[bl]
                bl -= 1

        else:
            while bl > 0:
                if (a >> (bl-1)) & 1:
                    if mine[bl] == 0:
                        print(1)
                        break
                    a ^= mine[bl]
                bl -= 1
            else:
                continue
            break
    else:
        print(0)

Submission status: Accepted

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

def least_bit_set(x):
	return x & (-x)


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0



#values = [1, 5, 8, 2, 10]
#eliminated_values = eliminate(values)
#print(eliminated_values)
#x = int(input())
#print(in_span(x, eliminated_values))

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
		else:
			elim = eliminate(values)
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)

Submission status: Accepted

Solution code:
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = list(map(int, input()))
    
    for i in range(N-1, -1, -1):
        ai = A[i]
        if ai==0:
            continue
        top = ai.bit_length() - 1
        assert ai & 1<<top
        for j in range(i-1, -1, -1):
            if A[j] >> top & 1:
                A[j] ^= ai
    for a, c in zip(A[::-1], S[::-1]):
        if c==1 and a:
            break
    else:
        print("0")
        continue
    print("1")

Submission status: Accepted

Solution code:
def collapse(A):
    R = []
    a = max(A)
    n = a.bit_length()
    B = [set() for _ in range(n)]
    for a in A:
        B[a.bit_length()].add(a)
    for i in reversed(range(n)):
        if not B[i]:
            continue
        b = B[i].pop()
        R.append(b)
        for k in B[i]:
            k ^= b
            B[k.bit_length()].add(k)
    return R

def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            n = a.bit_length() - 1
            while a != 0:
                if B[n] == 0:
                    return 1
                a ^= B[n]
                n = a.bit_length() - 1
        else:
            n = a.bit_length() - 1
            while a != 0 and B[n] != 0:
                a ^= B[n]
                n = a.bit_length() - 1
            if a == 0:
                continue
            B[n] = a
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    for t in range(int(input())):
        N = int(input())
        A = list(map(int, input().split()))
        S = input().rstrip('\n')
        A.reverse()
        S = S[::-1]

        A0 = [0] * 60
        A1 = [0] * 60
        zero = 0
        one = 0
        for i, a in enumerate(A):
            if S[i] == "0":
                for j in range(60):
                    A0[j] ^= ((a >> j & 1) << zero)
                zero += 1
            else:
                for j in range(60):
                    A1[j] ^= ((a >> j & 1) << one)
                one += 1

        B = [0] * 60
        for i in range(60):
            B[i] = A0[i] + (A1[i] << zero)

        rnk = 0
        for i in range(zero):
            #print(B)
            for j in range(rnk, 60):
                if B[j] >> i & 1:
                    B[j], B[rnk] = B[rnk], B[j]
                    b = B[rnk]
                    #print(b)
                    for jj in range(60):
                        if jj == rnk:
                            continue
                        if B[jj] >> i & 1:
                            B[jj] ^= b
                    rnk += 1
                    break

        cnt0 = 0
        cnt1 = zero
        r = -1
        win = 0
        for s in S:
            if s == "0":
                if r+1 >= len(B):
                    break
                if B[r+1] >> cnt0 & 1:
                    r += 1
                cnt0 += 1
            else:
                rr = -1
                for j in range(60):
                    if B[j] >> cnt1 & 1:
                        rr = j
                if rr > r:
                    win = 1
                    break
                cnt1 += 1
        print(win)


if __name__ == '__main__':
    main()

Submission status: Accepted

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, last_col, rank):
    # 掃き出し法
    for col in range(last_col, mat.shape[1] - 1):
        if rank >= DIGIT:
            break
        last_col = col
        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, last_col, rank
    else:
        return True, last_col, rank


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

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

    a_mat = []
    for d in reversed(range(DIGIT)):
        a_mat.append(A >> d & 1)
    mat = np.array(a_mat).astype(bool)

    rank = 0
    for col in range(N):
        if S[col]:
            # check
            if mat[rank:, col].any():
                # 1のかち
                return True
        if rank >= DIGIT:
            return False
        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
    return False


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(int(ans))

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




def least_bit_set(x):
    return x & (-x)


def delete_zeros_from(values, start):
    i = start
    for j in range(start, len(values)):
        if values[j] != 0:
            values[i] = values[j]
            i += 1
    del values[i:]


def eliminate(values):
    values = list(values)
    i = 0
    while True:
        delete_zeros_from(values, i)
        if i >= len(values):
            return values
        j = i
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) < least_bit_set(values[j]):
                j = k
        values[i], values[j] = (values[j], values[i])
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) == least_bit_set(values[i]):
                values[k] ^= values[i]
        i += 1


def in_span(x, eliminated_values):
    for y in eliminated_values:
        if least_bit_set(y) & x != 0:
            x ^= y
    return x == 0


t = I()
for _ in range(t):
    n = I()
    A = LI()
    s = S()
    flg = 0
    values = []
    for j in range(n - 1, -1, -1):
        if int(s[j]) == 0:
            values += [A[j]]
            values = eliminate(values)
        else:
            if not in_span(A[j], values):
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
import bisect
from itertools import accumulate

T = int(input())

for _ in range(T):
    N = int(input())
    As = list(map(int, input().split()))
    S = input()
    possible_xor = []
    if S[-1] == '1':
        print(1)
        continue
    flg = True
    for c, A in reversed(list(zip(S, As))):
        if c == '0':
            for xor in possible_xor[::-1]:
                if A.bit_length() == xor.bit_length():
                    A ^= xor
                elif A > xor:
                    break
            possible_xor.insert(bisect.bisect_left(possible_xor, A), A)
        else:
            for xor in possible_xor[::-1]:
                if A.bit_length() == xor.bit_length():
                    A ^= xor
            if A != 0:
                flg = False
                break
    if flg:
        print(0)
    else:
        print(1)

Submission status: Accepted

Solution code:
def base(a, f=False):
    k = 0
    for i in range(64):
        for ind in range(k, len(a)):
            j = a[ind]
            if (j >> i) & 1 == 1:
                break
        else:
            continue

        a[ind], a[k] = a[k], a[ind]
        for ind, j in enumerate(a):
            if ind == k:
                continue
            if (j >> i) & 1 == 1:
                a[ind] ^= a[k]
        k += 1
        if k >= len(a):
            break
    return a[:k]


t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    s = input()

    b = []
    for i in reversed(range(n)):
        if s[i] == '0':
            b = base(b + [a[i]])

        else:
            c = base(b[:] + [a[i]])
            if len(c) != len(b):
                print(1)
                break

    else:
        print(0)

Submission status: Accepted

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

T=int(input())

def base(B):

    L=len(B)
    flag=1
    
    while flag:
        B.sort(reverse=True)
        
        flag=0

        for i in range(L):
            for j in range(i+1,L):
                if B[i]^B[j]<B[i]:
                    B[i]=B[i]^B[j]
                    flag=1
                    break
            if flag:
                break
    return B     

def rep(x):
    flag=1

    while flag:
        flag=0
        for b in B:
            if b^x<x:
                x=b^x
                flag=1
                break
    return x

for tests in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    B=[]
    S=input().strip()

    flag=1

    for i in range(N-1,-1,-1):
        if flag==0:
            break
        if S[i]=="0":
            v=rep(A[i])

            if v==0:
                continue
            B.append(v)
            B=base(B)

        else:
            if rep(A[i])!=0:
                print(1)
                flag=0
                break

    if flag:
        print(0)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
T = int(readline())
Ans = [None]*T
for qu in range(T):
    N = int(readline())
    A = list(map(int, readline().split()))
    S = list(map(int, readline().strip()))
    
    if len(set(A)) == 1:
        Ans[qu] = S[-1]
        continue
    
    if S[-1] == 1:
        Ans[qu] = 1
        continue
    
    stack = [0]*61
    for i in range(N-1, -1, -1):
        a = A[i]
        for j in range(60, -1, -1):
            if a&(1<<j):
                a ^= stack[j]
        
        if S[i] == 0:
            if a:
                stack[a.bit_length()-1] = a
            else:
                continue
        else:
            if a:
                Ans[qu] = 1
                break
    else:
        Ans[qu] = 0

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

Submission status: Accepted

Solution code:
import sys

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

def solve():
    INT_BITS = 64
    n = ni()
    a = nl()[::-1]
    s = ns()[::-1]
    lis = [0]*64
    for i in range(n):
        if s[i] == '1':
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                print(1)
                return
        else:
            c = a[i]
            for x in lis[::-1]:
                if x == 0:
                    continue
                if c & (1 << (x.bit_length() - 1)):
                    c ^= x
            if c:
                lis[c.bit_length() - 1] = c
    print(0)
    return

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def calcSpace():
    H = []
    hpush = lambda x: heappush(H, -x)
    hpop = lambda: -heappop(H)
    for x in X:
        hpush(x)
    
    E = [0] * 60
    while H:
        x = hpop()
        b = x.bit_length() - 1
        if E[b]:
            x ^= E[b]
            if x: hpush(x)
        else:
            E[b] = x
    
    return E
    
def chk(y):
    y0 = y
    for i in range(60)[::-1]:
        if y >> i & 1:
            if V[i]:
                y ^= V[i]
                # print("chk", y0, "OK", V)
                if y == 0: return 1
            else:
                return 0

def chk_all():
    for y in Y:
        if chk(y) == 0:
            return 1
            break
    else:
        return 0
    
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()]
    
    if 0:
        print("N =", N)
        print("A =", A)
        print("S =", S)
    
    X = []
    Y = []
    i = N - 1
    ans = 0
    while i >= 0:
        while i >= 0:
            if S[i]: break
            X.append(A[i])
            i -= 1
        while i >= 0:
            if S[i] == 0: break
            Y.append(A[i])
            i -= 1

            V = calcSpace()
            # print("X =", X)
            # print("Y =", Y)
            # print("V =", V)
            if chk_all():
                ans = 1
                i = -1
    print(ans)

Submission status: Accepted

Solution code:
import sys
from numba import njit
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8,)', cache=True)
def keta(x):
    ret = -1
    while x >= 1:
        x >>= 1
        ret += 1
    return ret

@njit('(i8,i8[::1],i4[::1])', cache=True)
def solve(N, A, S):
    if np.all(S == 0):
        return True
    if S[-1] == 1:
        if A[-1] == 0:
            return solve(N - 1, A[:-1], S[:-1])
        else:
            return False
    # .....10000
    i = np.where(S == 1)[0].max() + 1
    A1 = A[:i]
    B = A[i:]
    while True:
        B = B[B != 0]
        if len(B) == 0:
            break
        x = B.max()
        k = keta(x)
        A1 ^= ((A1 >> k) & 1) * x
        B ^= ((B >> k) & 1) * x
    N = len(A1)
    return solve(N, A1, S[:N])

def main():
    T = int(readline())
    for _ in range(T):
        N = int(readline())
        A = np.array(readline().split(), np.int64)
        S = np.array(list(readline().decode().rstrip()), np.int32)
        x = 0 if solve(N, A, S) else 1
        print(x)

main()