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:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline




def solve():
    def normalize(v,basis):
        for b in basis:
            if v > v^b: v ^= b
        return v
    
    n, = map(int,readline().split())
    *a, = map(int,readline().split())
    s = input()
    
    basis = []
    b0 = []

    for e,si in zip(a[::-1],s[::-1]):
        if si=="0":
        	for b in basis:
        	    if e > e^b: e ^= b
        	if e: basis.append(e)

        if si=="1":
            v = normalize(e,basis)
            if v!=0:
                print(1)
                return

    
    print(0)
    return
        
        


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

Submission status: Runtime Error

Solution code:

import sys, io, os, re
import bisect
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 = array2(N+1, 1, 0)
    for i in range(N-1, -1, -1):
        print(i, dp)
        if S[i] == "0":
            dp[i] = dp[i+1] + [x^A[i] for x in dp[i+1] if x^A[i] not in dp[i]]

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

    print("0")

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

Submission status: Runtime Error

Solution code:
def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


def gauss_jordan_mod(A, mod):
    EPS = 1e-8
    n = len(A)
    m = len(A[0])
    for i in range(n):
        if len(A[i]) != m:
            return "Error!"

    for i in range(n):
        for j in range(m):
            A[i][j] %= mod

    rank = 0
    for i in range(n):
        pivot = i
        for k in range(i, n):
            if abs(A[k][i]) > abs(A[pivot][i]):
                pivot = k
        A[i], A[pivot] = A[pivot], A[i]
        if abs(A[i][i]) < EPS:
            continue
        rank += 1
        s = inv(A[i][i], mod)
        for j in range(i, m):
            A[i][j] *= s
            A[i][j] %= mod
        for k in range(n):
            if k != i:
                s = A[k][i]
                for j in range(i, m):
                    A[k][j] -= s * A[i][j]
                    A[k][j] %= mod
    return A, rank


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    s = input()

    A = []
    rank = 0
    for i in range(n-1, -1, -1):
        cur = []
        for k in range(62):
            cur.append(a[i] >> k & 1)

        if s[i] == '1':
            B, rank_nxt = gauss_jordan_mod(A + [cur], 2)
            if rank_nxt > rank:
                return 1
        else:
            A, rank = gauss_jordan_mod(A + [cur], 2)
    return 0


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

Submission status: Runtime Error

Solution code:
def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


def gauss_jordan_mod(A, mod):
    EPS = 1e-8
    n = len(A)
    m = len(A[0])
    for i in range(n):
        if len(A[i]) != m:
            return "Error!"

    for i in range(n):
        for j in range(m):
            A[i][j] %= mod

    rank = 0
    for i in range(n):
        pivot = i
        for k in range(i, n):
            if abs(A[k][i]) > abs(A[pivot][i]):
                pivot = k
        A[i], A[pivot] = A[pivot], A[i]
        if abs(A[i][i]) < EPS:
            continue
        rank += 1
        s = inv(A[i][i], mod)
        for j in range(i, m):
            A[i][j] *= s
            A[i][j] %= mod
        for k in range(n):
            if k != i:
                s = A[k][i]
                for j in range(i, m):
                    A[k][j] -= s * A[i][j]
                    A[k][j] %= mod
    return A, rank


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    s = input()

    A = [[0 for _ in range(62)]]
    rank = 0
    for i in range(n-1, -1, -1):
        cur = []
        for k in range(62):
            cur.append(a[i] >> k & 1)

        if s[i] == '1':
            B, rank_nxt = gauss_jordan_mod(A + [cur], 2)
            if rank_nxt > rank:
                return 1
        else:
            A, rank = gauss_jordan_mod(A + [cur], 2)
    return 0


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

Submission status: Runtime Error

Solution code:
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

Submission status: Runtime Error

Solution code:
T = int(input())

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

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

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

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

Submission status: Runtime Error

Solution code:

t = int(input())
n = []
alist = []
s = []
for i in range(t):
    n.append(int(input()))
    alist.append(input())
    s.append(input())

for ti in range(t):
    xor_number = list(map(int,alist[ti].split()))
    people = list(map(int,list(s[ti])))
    dp = [set()] * (n[ti]+1)
    dp[n[ti]].add(0)
    for i in range(n[ti]-1,-1,-1):
        if people[i] == 1:
            if xor_number[i] in dp[i+i]:
                dp[i] = dp[i+1]
            else:
                dp[0] = None
                break
        if people[i] == 0:
            dp[i] = dp[i+1]
            dp[i].add(xor_number[i])
            new = set()
            if dp[i] != None:
                for j in dp[i]:
                    new.add(xor_number[i] ^ j )    
                dp[i] = dp[i].union(new)
    
    #make max in one
    if dp[i] == None:
        print(1)
    else: 
        print(0)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
def eprint(*args):
    print(*args, file=sys.stderr)
zz=0
from math import *
import copy
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def bo(i):
	return ord(i)-ord('a')
from copy import *
from bisect import *	

from itertools import permutations 
def check(p):
	for i in range(n-1,-1,-1):  
		if a[i]&(1<<p):
			if s[i]=='0':
				return 0
			else:
				return 1
	return 0			



t=fi()
while t>0:
	t-=1
	n=fi()
	a=li()
	s=si()
	flag=0
	for j in range(70):
		flag|=check(j)
	print(flag)

Submission status: Runtime Error

Solution code:
zfrom sys import stdin
def main(n,a,s):
  man0winset=set([0])
  if s[-1]=="1":
    print(1)
    return
  for orders in range(n-1,-1,-1):
    man = s[orders]
    amn = a[orders]
    if  amn == 0:
       continue
    if man=="0":
      man0winset = man0winset | {x^amn for x in man0winset}
    else:
      if amn not in man0winset:
        print(1)
        return
  if 0 in man0winset:
    print(0)
  else:
    print(1)
  
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,stdin.readline().split()))
  s=input()
  main(n,a,s)

Submission status: Runtime Error

Solution code:
def resolve():
	# T: test case数
	T = int(input())

	# test caseの実行
	for _ in range(T):
		# N: round数
		N = int(input())
		# XORする数
		A = input().split()
		# 人0 or 1
		S = list(input())

		# dpテーブル宣言
		# DP[i] = {t|t in DP[i-1] かつ i=Nでx=0になる}
		# 最後のroundで0になるケースを考えるので
		dp = {0}
		# 後ろから考える
		for i in range(N-1, -1, -1):
			a = int(A[i])
			# プレーヤー0の場合
			if S[i] == '0':
				# 解説pdfより、DP[i] = DP[i+1] U {v^a|v in DP[i+1]}
				dp = dp | {v^a for v in dp}
			# プレーヤー1の場合
			elif a not in dp:
				# プレーヤー１の勝ち？
				dp = {}
		# x_0=0 で始まり、dp[0]はx_N=0になる場合の直前のxの値なので、
		if 0 in dp:
			print('0')
		else:
			print('1')

resolve()

Submission status: Runtime Error

Solution code:
def resolve():
	# T: test case数
	T = int(input())

	# test caseの実行
	for t in range(T):
		# N: round数
		N = int(input())
		# XORする数
		A = input().split()
		# 人0 or 1
		S = list(input())

		# dpテーブル宣言
		# DP[i] = {t|t in DP[i-1] かつ i=Nでx=0になる}
		dp = [-1] * (N+1)
		# 最後のroundで0になるケースを考えるので
		dp[N] = {0}
		# 後ろから考える
		for i in range(N-1, -1, -1):
			a = int(A[i])
			# print(f't={t}, i={i}, a={a}, S={S[i]}', file=sys.stderr)
			# プレーヤー0の場合
			if S[i] == '0':
				# 解説pdfより、DP[i] = DP[i+1] U {v^a|v in DP[i+1]}
				dp[i] = dp[i+1] | {v^a for v in dp[i+1]}
			# プレーヤー1の場合
			elif a in dp[i+1]:
				# 何もしない
				dp[i] = dp[i+1]
			else:
				# プレーヤー１の勝ち？
				dp[i] = {}
		# x_0=0 で始まり、dp[0]はx_N=0になる場合の直前のxの値なので、
		if 0 in dp[0]:
			print('0')
		else:
			print('1')

resolve()

Submission status: Runtime Error

Solution code:
z=0
n=0
s=input()
l=[]
for i in range(len(s)):
	if s[i]=="0":
		z+=1
	elif s[i]=="1":
		n+=1
	else:
		if z>n:
			n+=1
			q="1"
		elif z<n:
			z+=1
			q="0"
		else:
			if s[i-1]=="1" or (i<len(s)-1 and s[i+1]=="1"):
				z+=1
				q="0"
			elif s[i-1]=="0" or (i<len(s)-1 and s[i+1]=="0"):
				n+=1
				q="1"
			else:
				if q=="1":
					z+=1
					q="0"
				else:
					n+=1
					q="1"
	l.append(abs(z-n))
print(max(l))

Submission status: Runtime Error

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
#from collections import deque,defaultdict
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
R = 10**9 + 7

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[k]
        for j in range(len(d)):
            if d[j]&b != 0:
                d[j] ^= c[k]
    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: Runtime Error

Solution code:
import numpy as np
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    matrix=np.zeros((60,1))
    for i in range(n-1,-1,-1):
        ne=np.array([(a[i]>>j)&1 for j in range(60)])
        matrix=np.c_[matrix,ne]
        col=matrix.shape[1]
        ra=np.linalg.matrix_rank(matrix) 
        if s[i]=="0":
            if col!=ra+1:
                matrix=np.delete(matrix,col,1)
        else:
            if col==ra+1:
                print(1)
                break
    else:
        print(0)

Submission status: Runtime Error

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

Submission status: Runtime Error

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(q)
        q = set(q) | task
        q = standard_form(list(q))
        q = set(q)
        if task != task | q:
            win = "1"

    print(win)

Submission status: Runtime Error

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: Runtime Error

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 memo_0:
                if val & num == num:
                    val -= num
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            hand.append(val)
            # 手持ちは基底で管理するので掃き出し法を行う
            hand = xor_gauss_jordan(memo_0)


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

Submission status: Runtime Error

Solution code:
def solve(n, a_list, s):

    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            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: Runtime Error

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

    def f(i, x):
        if i + 1 == n and s[i] == '0':
            return x == 0
        if f(i + 1, x):
            return False
        if f(i + 1, x ^ a[i]):
            return False
        return False

    if f(0, 0):
        ans.append(0)
    else:
        ans.append(1)
    
for j in ans:
    print(j)
    ans = []
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = str(input())

    def f(i, x):
        if i + 1 == n and s[i] == '0':
            return x == 0
        if f(i + 1, x):
            return False
        if f(i + 1, x ^ a[i]):
            return False
        return False

    if f(0, 0):
        ans.append(0)
    else:
        ans.append(1)
    
for j in ans:
    print(j)

Submission status: Runtime Error

Solution code:
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
        int t;
        scanf("%d", &t);
        ll a[200], cnt0[70], cnt1[70];
        while(t--){
                int n;
                scanf("%d", &n);
                REP(i, 0, n) scanf("%ld", &a[i]);
                REP(i, 0, 70) cnt0[i] = cnt1[i] = 0;
                char s[n+1];
                scanf("%s", s);

                for(int i=n-1; i>=0; i--){
                        if(s[i]=='0'){
                                int x = a[i];
                                for(int j=0; x; j++, x>>=1){
                                        cnt0[j] |= ((x&1) << (n-1-i));
                                }
                        }else{
                                int x = a[i];
                                for(int j=0; x; j++, x>>=1){
                                        cnt1[j] |= ((x&1) << (n-1-i));
                                }
                                bool ok = true;
                                REP(I, 0, 70) REP(J, 0, 70) if(cnt0[I]==cnt0[J]) {
                                        REP(K, 0, 70) REP(L, 0, 70) if(cnt1[K]!=cnt1[L]) {
                                                puts("1");
                                                goto ret;
                                        }
                                }
                        }
                }
                puts("1");
                ret:;
        }

        return 0;
}

Submission status: Runtime Error

Solution code:
wa

Submission status: Runtime Error

Solution code:
T= int(input())
 
a = []
b = []
 
for i in range(T):
  N = int(input())
  l = list(map(int, input().split())
  k = str(input())
  b.append(N)
  b.append(l)
  b.append(k)
  a.append(b)
  b = []
 
for i in range(T):
  m = a[i][1]
  s = a[i][2]
  index = s.rfind('1')
  if s[-1] == 1:
     print(1)
  elif s[-1] == 0 and m[-1] == 1:
     print(0)
  elif not "1" in s:
     print(0)
  elif "1" in l[-1*index:]:
     print(0)
  else:
     print(1)

Submission status: Runtime Error

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

    def f(i, x):
        if i + 1 == n and s[i] == '0':
            return x == 0
        if f(i + 1, x):
            return True
        if f(i + 1, x ^ a[i]):
            return True
        return False

    if f(0, 0):
        ans.append(0)
    else:
        ans.append(1)
    
for j in ans:
    print(j)

Submission status: Runtime Error

Solution code:
T= int(input())

a = []
b = []

for i in range(T):
  N = int(input())
  l = list(map(int, input().split())
  S = str(input())
  b.append(N)
  b.append(l)
  b.append(S)
  a.append(b)
  b = []

for i in range(T):
  m = a[i][1]
  s = a[i][2]
  index = s.rfind('1')
  if s[-1] == 1:
     print(1)
  elif s[-1] == 0 and m[-1] == 1:
     print(0)
  elif not "1" in s:
     print(0)
  elif "1" in l[-1*index:]:
     print(0)
  else:
     print(1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def standard_form(A):
    for k in range(60,-1,-1):
        bit = 1<<k
        exists = A&bit==bit
        used = A>2*bit
        i = np.where(exists & ~used)[0]
        if len(i) == 0:
            continue
        i = i[0]
        x = A[i]
        A[exists] ^= x
        A[i] = x
    return A



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(np.array(q, np.int64))
                task = task | set(q)
                task = standard_form(np.array(list(task), np.int64))
                task = set(task)
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                q = set(q) | task
                q = standard_form(np.array(list(q), np.int64))
                q = set(q)
                if task != task | q:
                    win = "1"
                    break

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

    if now == "1":
        q = standard_form(np.array(q, np.int64))
        q = set(q) | task
        if task != task | set(standard_form(np.array(list(q), np.int64))):
            win = "1"

    print(win)

Submission status: Runtime Error

Solution code:
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    key = int(s[-1])
    wset = {0}
    setlist = []#逆順になる
    manlist = []#逆順になる
    index = 0
    if(key == 1):
        print(1)
    else:
        for j in range(n):
            temp = int(s[-(j+1)])
            if(temp == key):
                tempset = set()
                for k in wset:
                    tempset.add(k ^ a[-(j+1)])
                wset = wset | tempset
            else:
                setlist.append(wset)
                manlist.append(key)
                index += 1
                if(key == 1):
                    if(setlist[index] - setlist[index-1] != set()):
                        print(1)
                        break
                key = temp
                wset = {0, a[-(j+1)]}
        setlist.append(wset)
        manlist.append(key)
        if(manlist[-1] == 1):
            if(setlist[-1] - setlist[-2] != set()):
                print(1)
            else:
                print(0)
        else:
            print(0)

Submission status: Runtime Error

Solution code:
a =[]
        k = 1
        while S[-k] == "0" :
            a2 = bin(A[-k])[2:]
            a2 = a2.zfill(keta)
           
            a2 = list(a2)
            a2 = list(map(int,a2))
            # print(a2)
            a.append(a2)
            k += 1
            if k > n:
                break
        a = np.matrix(a)
        rank = np.linalg.matrix_rank(a)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def standard_form(A):
    for k in range(60,-1,-1):
        bit = 1<<k
        exists = A&bit==bit
        used = A>2*bit
        i = np.where(exists & ~used)[0]
        if len(i) == 0:
            continue
        i = i[0]
        x = A[i]
        A[exists] ^= x
        A[i] = x
    return A



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(np.array(q, np.int64))
                task = task | set(q)
                task = standard_form(np.array(list(task), np.int64))
                task = set(task)
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                q = set(q) | task
                q = standard_form(np.array(list(q), np.int64))
                q = set(q)
                if task != task | q:
                    win = "1"
                    break

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

    if now == "1":
        q = standard_form(np.array(q, np.int64))
        q = set(q) | task
        q = standard_form(np.array(list(q), np.int64))
        q = set(q)
        if task != task | q:
            win = "1"

    print(win)

Submission status: Runtime Error

Solution code:
dit = 0


T = int(input())
for t in range(0,T):
    N = int(input())
    A = list(map(int, input().split()))
    S = str(input())   
    if S[N-1]=="1":
        print(1)
    else:
        if "1" not in S:
            print(0)
        else:
            for i in range(1,N):
                if S[-i]=="0":
                    dit = dit + 1
                    continue
                else:
                    break
            for j in range(1,dit+1):
                if A[-j]==0:
                    print(0)
                    break
                elif j != dit:
                    continue
                else:
                    print(1)

Submission status: Runtime Error

Solution code:
import deque

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

    for t in range(T):
        n = int(input())
        A = list(map(int, input().split()))
        s = input()
        if s[-1] == "1":
            print(1)
            break
        p1 = deque(0)
        p2 = deque(0)
        c1 = [A[i] for i in range(n) if s[i] == "0"]
        c2 = [A[i] for i in range(n) if s[i] == "1"]

        def dfs1(x, n):
            if n == len(c1):
                p1.append(x)
                return
            dfs1(x, n + 1)
            dfs1(x ^ c1[n], n + 1)

        def dfs2(x, n):
            if n == len(c2):
                p2.append(x)
                return
            dfs2(x, n + 1)
            dfs2(x ^ c2[n], n + 1)

        dfs1(0, 0)
        dfs2(0, 0)
        # print(set(p1), set(p2))
        if len(set(p1) ^ set(p2)) == 0:
            print(0)
        else:
            print(1)

resolve()

Submission status: Runtime Error

Solution code:
T= int(input())

a = []
b = []
for i in range(T):
  N = int(input())
  l = list(map(int, input().split())
  S = str(input())
  b.append(N)
  b.append(l)
  b.append(S)
  a.append(b)
  b = []

for i in range(T):
  m = a[i][1]
  s = a[i][2]
  index = s.rfind('1')
  if s[-1] == 1:
     print(1)
  elif s[-1] == 0 and m[-1] == 1:
     print(0)
  elif not "1" in s:
     print(0)
  elif "1" in l[-1*index]:
     print(0)
  else:
     print(1)