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

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def ref(N, A, S):
    if S[-1] == '1':
        return 1

    def f(i, x):
        if i == N:
            if x == 0:
                return 0
            else:
                return 1
        p = int(S[i])
        if f(i+1, x ^ A[i]) == p:
            return p
        if f(i+1, x) == p:
            return p
        return p ^ 1

    return f(0, 0)

def slv(N, A, S):
    if S[-1] == '1':
        return 1
    from random import choices
    al = [[], []]
    for s, a in zip(S, A):
        al[int(s)].append(a)

    al[0] = []
    for i in range(N-1, -1, -1):
        if S[i] == '1':
            break
        al[0].append(A[i])


    a0 = set(choices(list(set(al[0])), k=10))
    a1 = set(choices(list(set(al[1])), k=10))
    p0 = set([0])
    for a in a0:
        t = set()
        for v in p0:
            t.add(v ^ a)
        p0 |= t

    p1 = set([0])
    for a in a1:
        t = set()
        for v in p1:
            t.add(v ^ a)
        p1 |= t

    for v in p1:
        if v not in p0:
            return 1
    return 0


def main():
    T = read_int()
    for _ in range(T):
        N = read_int()
        A = read_int_n()
        S = read_str()
        print(slv(N, A, S))


    # import random
    # N = 35
    # A = [random.randint(1, 10**18) for _ in range(N)]
    # S = random.choices('01', k=N-1)
    # S.append('0')
    # print(ref(N, A, S))

    # while True:
    #     N = 30
    #     A = [random.randint(1, 1<<4) for _ in range(N)]
    #     S = random.choices('01', k=N-1)
    #     S.append('0')


    #     # A = [4, 16, 2, 10, 3, 13, 6, 4, 1, 3]
    #     # S = ['0', '0', '1', '0', '0', '0', '0', '0', '0', '0']
    #     print(A)
    #     print(S)
    #     a = slv(N, A, S)
    #     b = ref(N, A, S)
    #     if a != b:
    #         print(a, b)
    #         break


if __name__ == '__main__':
    main()

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 = []#逆順になる
    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)
            key = temp
            wset = {0, a[-(j+1)]}
        setlist.append(wset)
        manlist.append(key)
        if(manlist[0] == 1): print(1)
        else:
            for i in range(len(manlist)):
                if(manlist[i] == 0):
                    if(i+1 <len(manlist)):
                        if(setlist[i+1] - setlist[i] != set()):
                            print(1)
                            break
                    else:
                        print(0)
                elif(i+1 == len(manlist)):
                    print(0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def ref(N, A, S):
    if S[-1] == '1':
        return 1

    def f(i, x):
        if i == N:
            if x == 0:
                return 0
            else:
                return 1
        p = int(S[i])
        if f(i+1, x ^ A[i]) == p:
            return p
        if f(i+1, x) == p:
            return p
        return p ^ 1

    return f(0, 0)

def slv(N, A, S):
    if S[-1] == '1':
        return 1
    from random import choices
    al = [[], []]
    for s, a in zip(S, A):
        al[int(s)].append(a)

    al[0] = []
    for i in range(N-1, -1, -1):
        if S[i] == '1':
            break
        al[0].append(A[i])


    a0 = choices(list(set(al[0])), k=10)
    a1 = choices(list(set(al[1])), k=10)
    p0 = set([0])
    for a in a0:
        t = set()
        for v in p0:
            t.add(v ^ a)
        p0 |= t

    p1 = set([0])
    for a in a1:
        t = set()
        for v in p1:
            t.add(v ^ a)
        p1 |= t

    for v in p1:
        if v not in p0:
            return 1
    return 0


def main():
    T = read_int()
    for _ in range(T):
        N = read_int()
        A = read_int_n()
        S = read_str()
        print(slv(N, A, S))


    # import random
    # N = 35
    # A = [random.randint(1, 10**18) for _ in range(N)]
    # S = random.choices('01', k=N-1)
    # S.append('0')
    # print(ref(N, A, S))

    # while True:
    #     N = 30
    #     A = [random.randint(1, 1<<4) for _ in range(N)]
    #     S = random.choices('01', k=N-1)
    #     S.append('0')


    #     # A = [4, 16, 2, 10, 3, 13, 6, 4, 1, 3]
    #     # S = ['0', '0', '1', '0', '0', '0', '0', '0', '0', '0']
    #     print(A)
    #     print(S)
    #     a = slv(N, A, S)
    #     b = ref(N, A, S)
    #     if a != b:
    #         print(a, b)
    #         break


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	a = [int(j) for j in a]
	s = input()
	s = [int(j) for j in s]
	game = []
	val = []
	for j in range(n):
		temp = []
		state = 1
		while len(temp) != 2**n:
			for k in range(2**(n - (j + 1))):
				temp.append(state)
			if state == 0:
				state = 1
			else:
				state = 0
		game.append(temp)
	cn = 0
	while cn != 2**n:
		x = 0
		for j in range(n):
			if game[j][cn] == 1:
				x ^= a[j]
		val.append(x)
		cn += 1
	ind = -1
	turn = s[ind]
	while True:
		counts = Counter(val)
		if 0 in val:
			if counts[0] == len(val):
				print(f"{0}\n")
				break
			else:
				for j in range(0, len(val), 2):
					if turn == 0:
						val.insert(j, -1)
						first = val[j + 1]
						second = val[j + 2]
						if max(first, second) == first:
							val.pop(j + 1)
						else:
							val.pop(j + 2)
					else:
						val.insert(j, -1)
						first = val[j + 1]
						second = val[j + 2]
						if min(first, second) == first:
							val.pop(j + 1)
						else:
							val.pop(j + 2)
				while (-1) in val:
					val.remove(-1)
				ind -= 1
				turn = s[ind]
		else:
			print(f"{1}\n")
			break

Submission status: Runtime Error

Solution code:
def main():
    # XOR: 0,0->0  0,1->1  1,0->1  1,1->0
    # i桁目については常にa+bとaXORbは等しい
    # 人0はxを0に、人1はxを0以外にしたい
    # x=0にできる := 100110^100110=0;xと同じ値のA[i]で操作できる
    # 人1のあるパターンで、人0がいかなるパターンでもx!=0なら1
    # 人0のあるパターンで、人1がいかなるパターンでもx=0なら0
    # S[-1]が1ならans=1
    # そうでないとき、
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1]=='1':
        print(1)
        return
    else:
        # player0および1の作れる和リストを作成
        arr0,arr1 = set([]),set([])
        for i in range(N):
            if S[i]=='0':
                arr0 |= set([x+A[i] for x in list(arr0)])
                arr0.add(A[i])
            else:
                arr1 |= set([x+A[i] for x in list(arr1)])
                arr1.add(A[i])
        # リスト0がリスト1を内包するならplayer0の勝ち
        # そうでないならplayer1の勝ち
        s = arr1-arr0
        if s!={}:
            print(1)
        else:
            print(0)
main()

Submission status: Runtime Error

Solution code:
T=int(input())
for _ in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    hito0=[0]*60
    hito1=[0]*60
    for i in range(N):
        if S[i]=="0":
            a=A[i]
            for j in range(60):
                if a<=0:
                    break
                b=a%2
                a//=2
                hito0[j]+=b
        else:
            a=A[i]
            for j in range(60):
                if a<=0:
                    break
                b=a%2
                a//=2
                hito1[j]+=b
    ans=True
    for i in range(N):
        if hito0[i]==0 and hito1[i]>=1:
            ans=False
    if ans:
        print(0)
    else:
        print(1)

Submission status: Runtime Error

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

    def f(i, x):
        if i == n - 1 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 _ in ans:
    print(_)

Submission status: Runtime Error

Solution code:
import math

def kosu(kitei, k):
    n=len(kitei)
    lim = [0]*n
    for i in range(1, n):
        lim[i] = lim[i-1]|kitei[i-1]
    dp = [0]*(2**17)
    tmp = dp[:]
    dp[k] = 1
    for i in range(len(kitei))[::-1]:
        for j in range(lim[i]+1):
            tmp[j] = (dp[j^kitei[i]] + dp[j]) % (10**9+7)
        dp, tmp = tmp, dp
    return dp[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)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now)>0:
                pass
            else:
                answer=1
    return answer

t=int(input())
for i in range(t):
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()
    print(solve(n, alist, s))

Submission status: Runtime Error

Solution code:
ef popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def select(x2, A, S):
  num = len(bin(x2)) -2
  cand = []
  for i in range(num):
    if x2 >> i & 1:
      cand.append(i)
  cand_a = []
  for i, s in enumerate(S):
    if s == 0:
      a = A[i]
      num_a = len(bin(a)) -2
      for j in range(num_a):
        if a >> j & 1:
          cand_a.append(j)
  cand_a = set(cand_a)
  uni_cnt = 0
  for c in cand:
    if c not in cand_a:
      return True
  return False         
      
def solve(N, A, S):
  x = 0
  x2 = 0
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    if S[i] == 1:
      #if popcount(x2) >= popcount(x):
      #  x = x2
      #else:
      if select(x2, A, S):
        x = x2
    else:
      if popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    print(0)
  else:
    print(1)

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

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np
import math
T = int(stdin.readline().rstrip())

for i in range(T):
    # print("T=",i)
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    S = stdin.readline().rstrip()
    maxa = max(A)
    keta = int (math.log2(maxa) + 1)
    if S[-1] == "1":
        print(1)
    else:
        a =[]
        k = 1
        while S[-k] == "0":
            a.append(list(map(int,bin(A[-k])[2:])))
            k += 1
        a = np.matrix(a)
        rank = np.linalg.matrix_rank(a)
        if rank == keta:
            print(0)
        else:
            print(1)
        # print("keta=",keta)

Submission status: Runtime Error

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 B[r+1] >> cnt0 & 1:
                    r += 1
                cnt0 += 1
                if r == 60:
                    break
            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: Runtime Error

Solution code:
for i in range(int(input())):
    x = 0
    n = int(input())
    a = list(map(int, input().split()))
    s = str(input())

    def f(i, x):
        if i == n - 1 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):
        print('0')
    else:
        print('1')

Submission status: Runtime Error

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

Solution code:
t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    fir=[]
    sec=[]
    for j in range(n):
        if s[j]=="1":
            fir.append(a[j])
        else:
            sec.append(a[j])
    check=True
    if len(fir)==1 and check:
        check=False
        if (0^fir[0]) in sec:
            print(0)
        else:
            print(1)
    if check:
        fir.sort()
        hand=set([])
        for w in fir:
            tt=bin(w)
            cont=max(0,len(tt)-2-1)
            ju=pow(2,cont)
            if w>=ju:
                hand.add(cont)
            else:
                hand.add(max(0,cont-1))
        hand=list(hand)
        NG=set([])
        ht=len(hand)
        for h in range(ht-1):
            if hand[h]+1!=hand[h+1]:
                NG.add(pow(2,hand[h]+1))
                NG.add(pow(2,hand[h+1]))
        NG=list(NG)
        if NG==[]:
            hand.sort(reverse=True)
            dfg=pow(2,hand[0]+1)
            jflag=False
            for ss in sec:
                if ss<dfg:
                    jflag=True
            if jflag:
                print(0)
            else:
                print(1)
        else:
            NNG=[]
            xxz=len(NG)
            for xx in range(xxz-1):
                if xx%2==0:
                    NNG.append([NG[xx],NG[xx+1]])
            sec.sort()
            flag=True
            for left , right in NNG:
                if left<=sec[0] and sec[-1]<right:
                    flag=False
            if flag:
                print(0)
            else:
                print(1)

Submission status: Runtime Error

Solution code:
def zero(x,a):
    if a == 0 and x==0:
        return x
    elif x==0:
        return x
    elif a ==x:
        x = x^a
        return x
    else:
      	x = x^a
        return x

def notzero(x,a):
    if a == 0 and x==0:
        x = x^a
        return x
    elif x==0:
        x = x^a
        return x
    elif a ==x:
        return x
    else:
        x = x^a
        return x

T = int(input())

for t in range(T):
    N = int(input())
    A= list(map(int, input().split()))
    S = list(input())
    x = 0
    for i in range(len(S)):
        a = A[i]
        if S[i] == "1":
            x = notzero(x,a)
        else:
            x = zero(x,a)
    if x == 0:
        print(0)
    else:
        print(1)

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()
    fir=[]
    sec=[]
    for j in range(n):
        if s[j]=="1":
            fir.append(a[j])
        else:
            sec.append(a[j])
    check=True
    if len(fir)==1 and check:
        check=False
        if (0^fir[0]) in sec:
            print(0)
        else:
            print(1)
    if check:
        fir.sort()
        hand=set([])
        for w in fir:
            tt=bin(w)
            cont=max(0,len(tt)-2-1)
            ju=pow(2,cont)
            if w>=ju:
                hand.add(cont)
            else:
                hand.add(max(0,cont-1))
        hand=list(hand)
        NG=set([])
        ht=len(hand)
        for h in range(ht-1):
            if hand[h]+1!=hand[h+1]:
                NG.add(pow(2,hand[h]+1))
                NG.add(pow(2,hand[h+1]))
        NG=list(NG)
        NNG=[]
        xxz=len(NG)
        for xx in range(xxz-1):
            if xx%2==0:
                NNG.append([NG[xx],NG[xx+1]])
        sec.sort()
        flag=True
        for left , right in NNG:
            if left<=sec[0] and sec[-1]<=right:
                flag=False
        if flag:
            print(0)
        else:
            print(1)

Submission status: Runtime Error

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
def solve(N, arr, S):
    p1 = []
    p2 = []
    seta = {0}
    setb = {0}
    for i, c in enumerate(S):
        if c=='0':
            p1.append(arr[i])
        else:
            p2.append(arr[i])
    for n in p1:
        new_set = copy.copy(seta)
        for old_n in seta:
            new_set.add(n^old_n)
        seta = new_set
    for n in p2:
        new_set = copy.copy(setb)
        for old_n in setb:
            new_set.add(n^old_n)
        setb = new_set
    return all(n in seta for n in setb)
t = rri()
for _ in range(t):
    N = rri()
    arr = rrm()
    s = rr()
    ans = solve(N, arr, s)
    if ans:
        print (0)
    else:
        print(1)

Submission status: Runtime Error

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

	a1 = [a[i] for i in range(n) if s[i] == "1"]
	a0 = [a[i] for i in range(n) if s[i] == "0"]


	a1 = [list(map(int, "{0:b}".format(item))) for item in a1]
	a0 = [list(map(int, "{0:b}".format(item))) for item in a0]

	m = max([len(item) for item in a1])
	m = max(m, max([len(item) for item in a0]))

	for i in range(len(a1)):
		a1[i] = [0] * (m-len(a1[i])) + a1[i]

	for i in range(len(a0)):
		a0[i] = [0] * (m-len(a0[i])) + a0[i]

	# print("a0", a0)
	# print("a1", a1)

	# print("m", m)
	ones = [set(), set()]

	for i in range(2):
		arr = [a0, a1][i]
		ones_set = ones[i]
		for str_i in range(len(arr)):
			if arr[str_i][str_i:].count(1) > 0:
				max_one = arr[str_i][str_i:].index(1)
			else:
				max_one = -1
			pivot = str_i
			for pivot_c in range(str_i, len(arr)):
				if arr[pivot_c][str_i:].count(1) > 0 and arr[pivot_c][str_i:].index(1) < max_one:
					max_one = arr[pivot_c][str_i:].index(1)
					pivot = pivot_c

			# print("pivot", pivot)
			if max_one != -1:
				ones_set.add(m - str_i - max_one)

				for str_j in range(str_i, len(arr)):
					if str_j != pivot and (arr[str_j][str_i+max_one] == 1):
						for el_i in range(m):
							arr[str_j][el_i] = abs(arr[str_j][el_i] - arr[pivot][el_i])

			arr[pivot], arr[str_i] = arr[str_i], arr[pivot]

			# print("arr", arr)
		# print("ones_set[" + str(i) + "]", ones_set)

	zero_wins = True
	for one_pos in list(ones[1]):
		if one_pos in ones[0]:
			pass
		else:
			zero_wins = False
			break
	if zero_wins:
		print(0)
	else:
		print(1)

Submission status: Runtime Error

Solution code:
t=int(input())
#h1,m1,h2,m2,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

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

        k=0
        while s[n-1-k]=="0":
                k+=1
                
        for j in range(n-k):
                if s[j]=="0":
                        if x>x^a[j]:
                                x=x^a[j]
                else:
                        if x<x^a[j]:
                                x=x^a[j]


        b=set(a[n-k:])
        for j in range(k):
                if x in b:
                        x=0
                        break
                else:
                        if len(bin(x))>len(bin(x>x^a[j])):
                                x=x^a[j]

        if x==0:
                print(0)
        else:
                print(1)

Submission status: Runtime Error

Solution code:
def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)
    return result

T = int(input())
for t in range(T):
    n = input()
    t = input()
    s = input()
    a0 = [0]
    a1 = [0]
    s = s.rstrip("1")
    for i in range(len(s)):
        if s[i] == "0":
            for j in range(len(a0)):
                a0.append(int(a0[j]) ^ int(t[i*2]))
        elif s[i] == "1":
            for j in range(len(a1)):
                a1.append(int(a1[j]) ^ int(t[i*2]))
    if not list_difference(a1,a0):
        print("0")
    else:
        print("1")

Submission status: Runtime Error

Solution code:
t=int(input())
#h1,m1,h2,m2,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

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

        k=0
        while s[n-1-k]=="0":
                k+=1
                
        for j in range(n-k):
                if s[j]=="0":
                        if x>x^a[j]:
                                x=x^a[j]
                else:
                        if x<x^a[j]:
                                x=x^a[j]


        b=set(a[-k:])
        for j in range(k):
                if x in b:
                        x=0
                        break
                else:
                        if len(bin(x))>len(bin(x>x^a[j])):
                                x=x^a[j]

        if x==0:
                print(0)
        else:
                print(1)

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().rstrip()

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

    win = set()
    win.add(0)
    for j in range(len(S)-1, -1, -1):
        tmp = set()
        if S[j] == '0':
            for v in win:
                tmp.add(v ^ A[j])
            win += tmp
        else:
            for v in win:
                if v ^ A[j] not in win:
                    tmp.add(v)
            win -= tmp

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

Submission status: Runtime Error

Solution code:
t = int(input())
counter =0
x = 0
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input
    x = 0
    if '01' in s :
        counter +=1
if counter > 0:
    while True:
        pass

Submission status: Runtime Error

Solution code:
=int(input())
l1=[]
l2=[]
x=0
for i in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    s=input()
    for j in range(n):
        if s[j]=="1":
            if l[j]!=x:
                x=x^l[j]
            else:
                x=x
        if s[j]=="0":
            if l[j]==x:
                x = x ^ l[j]
            else:
                x=x
    l1.append(x)
for i in l1:
    if i!=0:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

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

def main():
    T = int(input())
    for i in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        # print(S,A)
        num0 = set()
        num1 = set()
        digits0 = [0] * 60# 人0の手番のときの各桁の和
        digits1 = [0] * 60# 人1の手番のときの各桁の和
        for j in range(N):
            if S[j] == '0':
                num0.add(A[j])
                for k in range(60):
                    digits0[k] += (A[j] >> k)&1
            else:
                num1.add(A[j])
                for k in range(60):
                    digits1[k] += (A[j] >> k)&1
        
        # それぞれのmax(A[i])の対数をとって1の方が大きいと１がかつ
        if math.log2(max(num0)+1) < math.log2(max(num1)+1):
            print(1)
        elif len(num0) < len(num1):# 個数の観点から
            print(1)
        else:
            # 桁の観点から
            flag = True
            # print(num0,digits0)
            # print(num1,digits1)
            for k in range(60):
                if digits0[k] == 0 and digits1[k] > 0:
                    print(1)
                    flag = False
                    break
            if flag:
                print(0)
        
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
T = int(input())

xor_result = 0

for i in range(T):
  N = int(input())
  A = [int(a) for a in input().split()]
  S = input()
  xor_result = case(xor_result, N, A, S, 0)
  if(xor_result == 0):
    print('0¥n')
  else:
    print('1¥n)
  result = 0
  
def case(r, n, a, s, index):
  temp = r
  if(n == index):
    return r
  a_case = a[index]
  s_case = s[index]
  index += 1
  
  if(s_case == '1'):
    if(r == 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
      if(temp == 0):
        temp = case(r, n, a, s, index)
  elif(s_case == '0'):
    if(r != 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
      if(temp != 0):
        temp = case(r, n, a, s, index)
  return temp