Problem:


Score : 400 points

Problem Statement

There are two persons, numbered 0 and 1, and a variable x whose initial value is 0.
The two persons now play a game.
The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

Person S_i does one of the following:

Replace x with x \oplus A_i, where \oplus represents bitwise XOR.

Do nothing.

Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

1 \leq T \leq 100

1 \leq N \leq 200

1 \leq A_i \leq 10^{18}

S is a string of length N consisting of 0 and 1.

All numbers in input are integers.

Input

Input is given from Standard Input in the following format.
The first line is as follows:

T

Then, T test cases follow.
Each test case is given in the following format:

N
A_1 A_2 \cdots A_N
S

Output

For each test case, print a line containing 0 if x becomes 0 at the end of the game, and 1 otherwise.

Sample Input 1

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

Sample Output 1

1
0
0

In the first test case, if Person 1 replaces x with 0 \oplus 1=1, we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0.

In the second test case, regardless of the choice of Person 1, Person 0 can make x=0 with a suitable choice.



Sample input:
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000


Sample output:
1
0
0

Submission status: Time Limit Exceeded

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

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
	else:
		i = 0
		while i < n and s[i] == "0":
			i += 1
		if i == n:
			print(0)
			continue
		ok = True
		o, z = {0}, {0}
		while i < n:
			while s[i] == "1":
				o_new = set()
				for x in o:
					o_new.add(x)
					o_new.add(x^a[i])
				o = o_new
				i += 1
			while i < n and s[i] == "0":
				z_new = set()
				for x in z:
					z_new.add(x)
					z_new.add(x^a[i])
				z = z_new
				i += 1
			if not o.issubset(z):
				ok = False
				break
		if ok:
			print(0)
		else:
			print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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 rec(i, cur):
    if memo[i][cur] != -1:
        return memo[i][cur]
    if i == N:
        if cur == 0:
            return 0
        else:
            return 1
    if S[i] == '0':
        res = 1
        res &= rec(i+1, cur)
        res &= rec(i+1, cur^A[i])
    else:
        res = 0
        res ^= rec(i+1, cur)
        res ^= rec(i+1, cur^A[i])
    memo[i][cur] = res
    return res

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()

    memo = [defaultdict(lambda: -1) for i in range(N+1)]
    ans = rec(0, 0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

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

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

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

			if f(i+1, v, True):
				return True

			return False
		else:
			if f(i+1, v^A[i], False):
				return False

			if f(i+1, v, False):
				return False

			return True

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

	print(0 if 0 in good else 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

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

    @lru_cache(maxsize=10**7)
    def rec(i,x):
        if i==N:
            return 1 if x>0 else 0
        if S[i]=='0':
            a = rec(i+1,x)
            if a == 0: ret = 0
            else:
                b = rec(i+1,x^A[i])
                ret = b
        else:
            a = rec(i+1,x)
            if a == 1: ret = 1
            else:
                b = rec(i+1,x^A[i])
                ret = b
        return ret
    print(rec(0,0))

Submission status: Time Limit Exceeded

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        cur = set([0])
        for a, s in zip(reversed(A), reversed(S)):
            if s == '1':
                nxt = set()
                for o in cur:
                    if o ^ a in cur:
                        nxt.add(o)
                cur = nxt
            else:
                nxt = [o ^ a for o in cur]
                for n in nxt:
                    cur.add(n)

        print('0' if 0 in cur else '1')
main()

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()
    can = {0}

    for i in range(n - 1, -1, -1):
        c = s[i]
        a = aaa[i]
        if c == '0':
            for b in list(can):
                can.add(a ^ b)
        else:
            new_can = set()
            for b in can:
                if a ^ b in can:
                    new_can.add(b)
            can = new_can
            if len(can) == 0:
                break

    if 0 in can:
        buf.append(0)
    else:
        buf.append(1)

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

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    s = input()
    can = {0}

    for i in range(n - 1, -1, -1):
        c = s[i]
        a = aaa[i]
        cannot = False
        if c == '0':
            for b in list(can):
                can.add(a ^ b)
        else:
            new_can = set()
            for b in can:
                if a ^ b in can:
                    new_can.add(b)
            can = new_can
            if len(can) == 0:
                break

    if 0 in can:
        buf.append(0)
    else:
        buf.append(1)

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

Submission status: Accepted

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

class BaseXor:
    def __init__(self):
        self.size = 0
        self.base = []
    
    def base_calculate(self, x, b):
        return min(x, x ^ b)

    def make_base(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        return x
    
    def change_base(self, x):
        for i in range(self.size):
            self.base[i] = self.base_calculate(self.base[i], x)
    
    def judge_linearly_dependent(self, x, value=False):
        x = self.make_base(x)
        res = True if x else False
        res = (res, x) if value else res
        return res
    
    def add_base(self, x):
        judge, x = self.judge_linearly_dependent(x, value=True)
        if judge:
            self.change_base(x)
            self.base.append(x)
            self.size += 1
            return True
        return False

def solve(n, a, s):
    base = BaseXor()
    judge = False
    for i in range(n-1, -1, -1):
        x = s[i]
        if x == "0":
            base.add_base(a[i])
        else:
            judge = base.judge_linearly_dependent(a[i])
            if judge:
                break
    
    res = 1 if judge else 0
    return res

def main():
    t = int(input())
    ans = [0]*t
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        res = solve(n, a, s)
        ans[i] = res
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

class BaseXor:
    def __init__(self):
        self.size = 0
        self.base = []
    
    def base_calculate(self, x, b):
        return min(x, x ^ b)

    def make_base(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        return x
    
    def change_base(self, x):
        for i in range(self.size):
            self.base[i] = self.base_calculate(self.base[i], x)

    def add_base(self, x):
        x = self.make_base(x)
        if x == 0:
            return False
        self.change_base(x)
        self.base.append(x)
        self.size += 1
        return True
    
    def judge_linearly_dependent(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        res = True if x else False
        return res

def solve(n, a, s):
    base = BaseXor()
    judge = False
    for i in range(n-1, -1, -1):
        x = s[i]
        if x == "0":
            base.add_base(a[i])
        else:
            judge = base.judge_linearly_dependent(a[i])
            if judge:
                break
    
    res = 1 if judge else 0
    return res

def main():
    t = int(input())
    ans = [0]*t
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        res = solve(n, a, s)
        ans[i] = res
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

class BaseXor:
    def __init__(self):
        self.size = 0
        self.base = []
    
    def base_calculate(self, x, b):
        return min(x, x ^ b)

    def make_base(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        return x
    
    def change_base(self, x):
        for i in range(self.size):
            self.base[i] = self.base_calculate(self.base[i], x)

    def add_base(self, x):
        x = self.make_base(x)
        if x == 0:
            return False
        self.change_base(x)
        self.base.append(x)
        self.base.sort()
        self.size += 1
        return True
    
    def judge_linearly_dependent(self, x):
        for b in self.base:
            x = self.base_calculate(x, b)
        res = True if x else False
        return res

def solve(n, a, s):
    base = BaseXor()
    judge = False
    for i in range(n-1, -1, -1):
        x = s[i]
        if x == "0":
            base.add_base(a[i])
        else:
            judge = base.judge_linearly_dependent(a[i])
            if judge:
                break
    
    res = 1 if judge else 0
    return res

def main():
    t = int(input())
    ans = [0]*t
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        res = solve(n, a, s)
        ans[i] = res
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f():
  n = int(input())
  A = list(map(int, input().split()))
  S = list(map(int, list(input())))
  basis = []
  for i in range(n-1, -1, -1):
    a, s = A[i], S[i]
    l = len(basis)
    for b in basis:
      a = min(a, a^b)
    if a:
      basis.append(a)
    if s and len(basis) != l:
      print(1)
      return
  print(0)

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
import random
def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    T = NI()
    for _ in range(T):
        N = NI()
        A = LI()
        S = SI()

        base = [0] * 60
        for i in range(N-1,-1,-1):
            x = A[i]
            if S[i] == '0':
                for j in range(60):
                    if base[j] > 0 and x & (1 << j):
                        x ^= base[j]

                for j in range(60):
                    if base[j] == 0 and x & (1<<j):
                        for k in range(60):
                            if base[k] & (1<<j):
                                base[k] ^= x
                        base[j] = x
                        break
            else:
                for j in range(60):
                    if base[j] > 0 and x & (1<<j):
                        x ^= base[j]
                if x > 0:
                    print(1)
                    break
        else:
            print(0)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def slv(n,a,s):
  base=[0]
  for i in range(n-1,-1,-1):
    v=a[i]
    for j in sorted(base,reverse=True):
      v=min(v,j^v)
    if v==0:
      pass
    else:
      if s[i]=='0':base.append(v)
      if s[i]=='1':return 1
  if base:return 0
  return 1

t=int(input())
n=[]
a=[]
s=[]
for _ in range(t):
  n.append(int(input()))
  a.append(list(map(int,input().split())))
  s.append(input())
for i in range(t):
  print(slv(n[i],a[i],s[i]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc045/tasks/agc045_a

A[i]が正なので、最後が人1ならば絶対1がかつ

あとは最後が0の場合を考える
→人0が作れない数字を作れればおk

Xorは戻る演算であることを考慮

◎仮説
1の持ってる数それぞれについて、0がそれ以降の数を使って作れるなら0の勝ち。
そうでないなら1の勝ち

まず、1が持っているある数に関して、それ以降で打ち消せることが必要十分条件であることの証明
それ以前に0が対策しておいたとする。1が使わなかった場合、0はそれ以降で対策を打ち消さなくてはいけない。
すなわち、1が行動した後にできる行動 = 対策のためにできる行動
なので、必要十分である

1が持つ複数の数字に関して、それぞれ後ろで打ち消せればいいことの証明
S,Tという2つの数があり、それぞれ後ろで打ち消せるとする。
SとTを打ち消すための集合を全部選ぶと、そのXorはS^Tとなるので打ち消せる
よって示された

あとは、O(N**2)で求められればおk
追加するときに、まだ分離できていない桁かつ1の桁を見つけて分離すればおk

2**60なので

"""

from sys import stdin

TT = int(stdin.readline())

for loop in range(TT):

    N = int(stdin.readline())
    A = list(map(int,stdin.readline().split()))
    S = stdin.readline()
    S = S[:-1]

    zerolis = []
    root = [None] * 60

    for i in range(N-1,-1,-1):

        #0の時、掃き出し法をして新たな基底にする
        if S[i] == "0":

            #今まで作った基底の位を消す
            now = A[i]
            for j in range(60):
                if root[j] != None and now & (2**j) > 0:
                    now ^= zerolis[root[j]]

            #新たな基底にできる桁を探索
            for j in range(60):
                if root[j] == None and now & (2**j) > 0:
                    
                    for k in range(len(zerolis)):
                        if zerolis[k] & (2**j) > 0:
                            zerolis[k] ^= now

                    root[j] = len(zerolis)
                    zerolis.append(now)
                    break

        else: #1の時、今までの基底で打ち消せるか調べる

            now = A[i]
            for j in range(60):
                if root[j] != None and now & (2**j) > 0:
                    now ^= zerolis[root[j]]

            if now != 0:
                print (1)
                break
    else:
        print (0)

Submission status: Accepted

Solution code:
# xor battle


def is_included(base, X):
    base.sort(reverse=True)
    V = X
    for x in base:
        V = min(V, V ^ x)
    return V


def solve():
    N = int(input())
    a = list(map(int, input().split()))[::-1]
    player = input()[::-1]
    basement = [0]
    for i in range(N):
        v = a[i]
        K = is_included(basement, v)
        if player[i] == "0":
            if K == 0:
                pass
            else:
                basement.append(K)
        else:
            if K == 0:
                pass
            else:
                return 1

    return 0


def main():
    T = int(input())
    for i in range(T):
        A = solve()
        print(A)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# xor battle


def is_included(base, X):
    base.sort(reverse=True)
    V = X
    for x in base:
        V = min(V, V ^ x)
    return V


def solve():
    N = int(input())
    a = list(map(int, input().split()))[::-1]
    player = input()[::-1]
    basement = [0]
    for i in range(N):
        v = a[i]
        K = is_included(basement, v)
        if player[i] == "0":
            if K == 0:
                pass
            else:
                basement.append(K)
        else:
            if K == 0:
                pass
            else:
                return 1

    return 0


def main():
    T = int(input())
    for i in range(T):
        A = solve()
        print(A)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc():
        n = int(readline())
        a = list(map(int, readline().split()))
        s = input()
        b = [-1] * 61

        for i in range(n - 1, -1, -1):
            x = a[i]
            if s[i] == "0":
                l = x.bit_length()
                if b[l - 1] == -1:
                    b[l - 1] = x
                else:
                    while b[l - 1] != -1 and x > 0:
                        x ^= b[l - 1]
                        l = x.bit_length()
                    if x != 0:
                        b[l - 1] = x
            else:
                xb = format(x, "b")[::-1]
                l = len(xb)
                cur = 0
                for j in range(l - 1, -1, -1):
                    bit = int(xb[j])
                    cur_bit = int(format(cur,"b").zfill(l)[::-1][j])
                    if bit ^ cur_bit == 1:
                        if b[j] != -1:
                            cur ^= b[j]
                        else:
                            return print(1)
        return print(0)

    t = int(readline())
    for _ in range(t):
        calc()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

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

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,vA,S):
	sZ = set({0,})
	for a,c in zip(vA[::-1],S[::-1]):
		v = a
		for z in reversed(sorted(list(sZ))):
			v = min(v, v^z)
			#if not N: print(z,v)##
		if c=="0":
			sZ |= {v,}
		elif v not in sZ:
			sZ = set({})
			break
		#else:
		#	pass	# sZ = sZ
		#if not N: print(sZ)##
	
	res = 1
	if sZ:
		res = 0
	
	#print(sZ)###
	print(res)


def main():
	T, = linput()
	for _ in "*"*T:
		N, = linput()
		vA = linput()
		S, = linput(str)
		sol(N, vA, S)

def ran():
	N = 200
	#N=6
	vRan = [random.randint(1,10) for _ in "*"*N]
	S = "".join(str(random.randint(0,1)) for _ in "*"*N)
	#print(max(vRan))#
	#vRan = [5, 7, 7, 3, 1, 7]###
	#S = "111000"###
	print(vRan,S)
	sol(N=0, vA=vRan, S=S)
	exit(0)
	
if __name__ == "__main__":
	#ran()
	main()

Submission status: Accepted

Solution code:
def solve(N, A, S):
    bit = [0] * 64
    for i in range(N-1,-1,-1):
        Ai = A[i]
        Si = S[i]
        while Ai:
            n = Ai.bit_length() -1
            if bit[n] == 0 and Si == '1':
                return 1
            elif bit[n] == 0 and Si == '0':
                bit[n] = Ai
                break
            Ai ^= bit[n]
    return 0

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class BaseF2:
    def  __init__(self, vs=None):
        """vs: list of vecotr in F2
        """
        self.base = []
        if vs is not None:
            for v in vs:
                tmp = v
                for u in self.base:
                    tmp = min(tmp, tmp^u)
                if tmp>0:
                    self.base.append(tmp)
    def insert(self, v):
        for u in self.base:
            v = min(v, v^u)
        if v>0:
            self.base.append(v)
    def check(self, v):
        for u in self.base:
            v = min(v, v^u)
        return v==0
    def clear(self):
        self.base = []
    
    
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    b0 = BaseF2()
    b1 = BaseF2()
    done = False
    for i in range(n-1, -1, -1):
        if s[i]=="1":
            b1.insert(a[i])
        else:
            b0.insert(a[i])
        for item in b1.base:
            if not b0.check(item):
                print(1)
                done = True
                break
        if done:
            break
    else:
        print(0)

Submission status: Accepted

Solution code:
T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            a = min(a, a ^ b)
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
T = int(input())
for i in range(T):
    n = int(input())
    A = list(map(int, input().split()))
    S = input()
    dp = []
    for j in reversed(range(n)):
        a = A[j]
        for x in dp:
            a = min(a, a^x)
        if a > 0:
            if S[j] == '0':
                dp.append(a)
            elif not A[j] in dp:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

Solution code:
def solve(N, A, S):
    dp = []
    for i in reversed(range(N)):
        x = A[i]
        for v in dp:
            x = min(x, v^x)
        if x > 0:
            if S[i] == "0":
                dp.append(x)
            else:
                return 1
    return 0

def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        ans[i] = solve(N, A, S)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    l = []
    ans = 0
    
    for a, s in zip(A[::-1], S[::-1]):
        for b in l:
            a = min(a, a^b)
        if a != 0:
            if s == '1':
                ans = 1
            l.append(a)
    
    print(ans)

Submission status: Accepted

Solution code:
def msb(x):
    cnt = 0
    while x:
        x >>= 1
        cnt += 1
    return cnt


def solve(n, a, s):
    # dp[i] = (i回目時点で最終的に0にできる数の集合)
    dp = [[] for _ in range(n + 1)]
    # dp[n] = [0]
    for i in reversed(range(n)):
        if s[i] == '0':
            x = a[i]
            dp[i] = dp[i + 1].copy()
            dp[i].sort(reverse=True)
            for j in range(len(dp[i])):
                x = min(x, x ^ dp[i][j])
            if x != 0:
                dp[i].append(x)
        else:
            x = a[i]
            dp[i + 1].sort(reverse=True)
            for j in range(len(dp[i + 1])):
                x = min(x, x ^ dp[i + 1][j])
            if x == 0:
                dp[i] = dp[i + 1].copy()
            else:
                return '1'
        # print(i, a[i], s[i], dp[i])
    # print(n, a, s)
    # print(*dp, sep='\n')
    if len(dp[0]) != 0:
        return '0'
    else:
        return '1'


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

Submission status: Accepted

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

    base=[]

    for i in range(n-1,-1,-1):
        v=a[i]

        for x in base:
            v=min(v,v^x)
        
        if v:
            if s[i]==0:
                base.append(v)
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

def solve(N, A, S):
    dp = [0]

    for i in range(N-1, -1, -1):
        #print(i, dp)
        ai = A[i]

        if S[i] == "0":
            # Pattern 1 -> TLE
            #dp += [x^A[i] for x in dp if x^A[i] not in dp]
            
            # Pattern 2 -> TLE
            #for x in dp:
            #    a = x ^ A[i]
            #    if bisect_left(dp, a) == bisect_right(dp, a):
            #        insort(dp, a)

            for d in dp:
                if ai > ai^d: ai ^= d
            if ai: dp.append(ai)

        if S[i] == "1":
            # Pattern 2 -> TLE
            #if A[i] not in dp:
            #    print("1")
            #    return

            for b in dp:
                if ai > ai^b: ai ^= b
            if ai:
                print("1")
                return

    print("0")

T = n1()
for _ in range(T):
    N = n1()
    A = nn()
    S = s1()
    solve(N, A, S)

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

def solve(N, A, S):
    dp = [0]

    for i in range(N-1, -1, -1):
        #print(i, dp)
        ai = A[i]
        if S[i] == "0":
            # Pattern 1 -> TLE
            #dp += [x^A[i] for x in dp if x^A[i] not in dp]
            
            # Pattern 2 -> TLE
            #for x in dp:
            #    a = x ^ A[i]
            #    if bisect_left(dp, a) == bisect_right(dp, a):
            #        insort(dp, a)

            for d in dp:
                if ai > ai^d: ai ^= d
            if ai: dp.append(ai)

        if S[i] == "1":
            #if A[i] not in dp:
            #    print("1")
            #    return

            for b in dp:
                if ai > ai^b: ai ^= b

            if ai != 0:
                print("1")
                return

    print("0")

T = n1()
for _ in range(T):
    N = n1()
    A = nn()
    S = s1()
    solve(N, A, S)

Submission status: Accepted

Solution code:
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:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 逆から, zero_cardsに数を貯めて行き、bitで0に出来るか
T = ir()
for _ in range(T):
    N = ir()
    A = lr()
    S = sr()
    zero_cards = []
    for a, person in zip(A[::-1], S[::-1]):
        for z in zero_cards:
            a = min(a, a^z)
        if a:
            if person == '1':
                print(1)
                break
            zero_cards.append(a)
    else:
        print(0)

Submission status: Accepted

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