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:
from itertools import groupby, chain
from operator import itemgetter


def sweep(l):
    result = []
    s = set(l)
    while s:
        a = max(s)
        b = 1 << (a.bit_length() - 1)
        s = {t ^ a if t >= b else t for t in s}
        s.discard(0)
        result.append([a, b])

    return result


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

    if s[-1] == '1':
        buf.append(1)
        continue

    grp = [list(map(itemgetter(1), itr)) for c, itr in groupby(zip(s, aaa), key=itemgetter(0))]
    if s[0] == '0':
        grp = grp[1:]
    grp1 = grp[0::2]
    grp0 = grp[1::2]
    erasable = [False] * sum(len(g) for g in grp1)
    for i in range(len(grp1)):
        l1 = list(chain(*grp1[:i + 1]))
        l0 = list(chain(*grp0[i:]))
        s0 = sweep(l0)

        for a, b in s0:
            for i in range(len(l1)):
                if l1[i] & b:
                    l1[i] ^= a

        for j, c in enumerate(l1):
            if c == 0:
                erasable[j] = True

    if all(erasable):
        buf.append(0)
    else:
        buf.append(1)


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

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
T = int(input())

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

    p0 = [0]
    p1 = [0]
    for i in range(len(S)):
        if S[i] == "0":
            p0.append(int(A[i]))
        else:
            p1.append(int(A[i]))

    # xorのリスト
    p1xor = copy.copy(p1) 
    comb = list(itertools.product([0,1],repeat=len(p1)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p1xor[i]
                if temp not in p1xor:
                   p1xor.append(temp)
    setp1 = set(p1xor)

    # xorのリスト
    p0xor = copy.copy(p0) 
    comb = list(itertools.product([0,1],repeat=len(p0)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p0xor[i]
                if temp not in p0xor:
                    p0xor.append(temp)

    setp0 = set(p0xor)
    flag = True
    for p in setp1:
        if p not in setp0:
            flag = False
    if flag == True:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

        k=0

        while s[n-1-k]=="0" and k<n:
                k+=1
                
        b=set([0])
        c=set([0])
        for j in range(n-k):
                if s[j]=="1":
                        c.add(a[j])

        for j in range(k):
                b.add(a[n-k+j])
                for p in list(b):
                        b.add(p^a[n-k+j])
        if c<=b:
                x=0
        else:
                x=1
                        
        if x==0:
                print(0)
        else:
                print(1)

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    t=int(input())
    for _ in range(t):
        st=time.time()
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                        break
                    if time.time()-st>0.0005:
                        print(1)
                        ans=1
                        break
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()

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()
    if S[-1]=='1':
        print(1)
        continue

    @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^A[i])
            if a == 0: ret = 0
            else:
                b = rec(i+1,x)
                ret = b
        else:
            a = rec(i+1,x^A[i])
            if a == 1: ret = 1
            else:
                b = rec(i+1,x)
                ret = b
        return ret
    print(rec(0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def dfs(bf, i, hlist, human):
    global idx
    n = hlist[i]
    tmp = bf^n
    if tmp not in human:
        human.add(tmp)
        if i+1 < idx:
            dfs(tmp, i+1, hlist, human)
    if i+1 < idx:
        dfs(bf, i+1, hlist, human)

def main():
    global idx
    T = int(readline())
    for _ in range(T):
        N = int(readline())
        A = list(map(int, readline().split()))
        S = list(readline()[:-1])
        # 最後がhuman1のときはhuman0は勝てない
        if S[:-1] == '1':
            print(1)
            continue
        human1 = set(); human0 = set()
        h1list = []; h0list = []
        for i, s in enumerate(S):
            a = A[i]
            if s == '1':
                h1list.append(a)
            else:
                h0list.append(a)
        # human0しか操作しないときは human1は勝てない
        if len(h1list) == 0:
            print(0)
            continue
        # human1しか操作しないときは, human0は勝てない
        if len(h0list) == 0:
            print(1)
            continue
        # human1 と human0 のそれぞれが作れる数を調べる
        idx = len(h1list)
        dfs(0, 0, h1list, human1)

        idx = len(h0list)
        dfs(0, 0, h0list, human0)

        # human0 が human1 よりも大きいなら human0が勝つ
        if len(human1 - human0) == 0:
            print(0)
        else:
            print(1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    t=int(input())
    for _ in range(t):
        st=time.time()
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                        break
                    if time.time()-st>0.005:
                        print(1)
                        ans=1
                        break
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def least_bit_set(x):
    return x & (-x)


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


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


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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    s = input()
    s = s[::-1]
    values = []
    for x in range(0,n):
        if s[x] == '0':
            values.append(a[x])
        else:
            if (in_span(a[x], values) == False):
                return 0
    return 1

def main():
    t = int(input())
    while t>0:
        if(solve()):
            print(0)
        else:
            print(1)
        t -= 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    t=int(input())
    for _ in range(t):
        st=time.time()
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                        break
                    if time.time()-st>0.015:
                        print(1)
                        ans=1
                        break
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
T = int(input())

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

    p0 = [0]
    p1 = [0]
    for i in range(len(S)):
        if S[i] == "0":
            p0.append(int(A[i]))
        else:
            p1.append(int(A[i]))

    # xorのリスト
    p1xor = copy.copy(p1) 
    comb = list(itertools.product([0,1],repeat=len(p1)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p1xor[i]
                if temp not in p1xor:
                   p1xor.append(temp)

    # xorのリスト
    p0xor = copy.copy(p0) 
    comb = list(itertools.product([0,1],repeat=len(p0)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p0xor[i]
                if temp not in p0xor:
                    p0xor.append(temp)

    flag = True
    for p in p1xor:
        if p not in p0xor:
            flag = False
    if flag == True:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from itertools import combinations


# 排他的論理和は高々いくつ未満か
def cnt_div_2(n):
    cnt = 0
    while n > 1:
        n //= 2
        cnt += 1
    return cnt + 1


# 全パターン試す。試しすぎないようにmax_lenでbreak
def calc_xor(a, arr, max_len):
    for i in range(2, len(a) + 1):
        tmp = combinations(a, i)
        for j in tmp:
            tmp_xxx = 0
            for k in j:
                tmp_xxx ^= k
            arr.add(tmp_xxx)
            if len(arr) >= max_len:
                break
        if len(arr) >= max_len:
            break
    return arr


t = int(input())

ans = []
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = list(map(int, input().rstrip()))

    # 最後が1なら絶対勝てない
    if s[-1] == 1:
        ans.append(1)
        continue

    # 1がなければ絶対勝てる
    elif s.count(1) == 0:
        ans.append(0)
        continue

    a0 = set()
    a1 = set()
    for i in range(n):
        if s[i] == 0:
            a0.add(a[i])
        else:
            a1.add(a[i])

    arr0 = copy.deepcopy(a0)
    arr1 = copy.deepcopy(a1)

    max_len_0 = 2**cnt_div_2(max(a0)) - 1
    max_len_1 = 2**cnt_div_2(max(a1)) - 1

    if max_len_1 > max_len_0:
        ans.append(1)
        continue

    arr0 = calc_xor(a0, arr0, max_len_0)
    arr1 = calc_xor(a1, arr1, max_len_1)

    if len(arr1 - arr0) == 0:
        ans.append(0)
        continue
    else:
        ans.append(1)
        continue

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections,math
sys.setrecursionlimit(1000000)

INF = float("inf")

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
    S = sys.stdin.readline().rstrip()
    a = []
    b = []
    n_0 = 0
    ab=0
    bb=0
    for i in range(N):
        if S[i] == '0':
            a.append(A[i])
            n_0+=1
            ab = A[i]|ab
        else:
            b.append(A[i])
            bb = A[i]|bb
    #print(S,A)
    if (ab & bb) != bb:
        print('1')
        continue
    S=['1']*(N-n_0)+['0']*n_0
    A=b+a
    #print(S,A)
    def backtrack(i,x):
        if i == N:
            return x==0
        if S[i] == '0':
            if x == 0:
                return True
            if backtrack(i+1,x^int(A[i])) == False and backtrack(i+1,x) == False:
                return False
            else:
                return True
        else:
            if backtrack(i+1,x^int(A[i])) == True and backtrack(i+1,x)==True:
                return True
            else:
            #if backtrack(i+1,x^int(A[i])) == False or backtrack(i+1,x)==False:
                return False

    if backtrack(0,0)==True:
        print("0")
    else:
        print("1")

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
T = int(input())

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

    p0 = [0]
    p1 = [0]
    for i in range(len(S)):
        if S[i] == "0":
            p0.append(int(A[i]))
        else:
            p1.append(int(A[i]))

    # xorのリスト
    p1xor = copy.copy(p1) 
    comb = list(itertools.product([0,1],repeat=len(p1)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p1xor[i]
                p1xor.append(temp)

    # xorのリスト
    p0xor = copy.copy(p0) 
    comb = list(itertools.product([0,1],repeat=len(p0)))
    for c in comb:
        temp = 0
        for i in range(len(c)):
            if c[i] == 1:
                temp = temp ^ p0xor[i]
                p0xor.append(temp)

    flag = True
    for p in p1xor:
        if p not in p0xor:
            flag = False
    if flag == True:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

def cum(lis):
    result = []
    for n in range(1,len(lis)+1):
        for conb in itertools.combinations(lis, n):
            result.append(list(conb)) #タプルをリスト型に変換
    return result

t = int(input())
x = 0

for i in range(t):
    list0 = []
    list1 = []
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    
    for j in range(n):
        if s[j] == "0":
            list0.append(a[j])
        else:
            list1.append(a[j])
    
    list0_v2 = cum(list0)
    list1_v2 = cum(list1)
    #print(list0_v2)
    
    ans0 = []
    ans1 = []
    
    #print(list0_v2[0][0])
    
    for j in range(len(list0_v2)):
        #print(list0_v2[j])
        tmp = 0
        for k in range(len(list0_v2[j])):
            if k == 0:
                tmp = int(list0_v2[j][0])
            else:
                tmp = (tmp ^ int(list0_v2[j][k]))
        ans0.append(tmp)
        
    for j in range(len(list1_v2)):
        #print(list0_v2[j])
        tmp = 0
        for k in range(len(list1_v2[j])):
            if k == 0:
                tmp = int(list1_v2[j][0])
            else:
                tmp = (tmp ^ int(list1_v2[j][k]))
        ans1.append(tmp)
    
    #print(ans0,ans1)
    if set(ans0) == set(ans1):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
for i in range(T):
 N=int(input())
 A = list(map(int,input().split()))
 S=input()
 if S[N-1]==1:
  print(1)
 else:
  wa=0
  t=N-1
  lst0=[]
  lst1=[]
  while t>=0:
   ct=0
   while ct<2 and t>=0:
    if int(S[t])==0:
     lst0.append(A[t])
     if ct==1:
      ct=2
    else:
     lst1.append(A[t])
     if ct==0:
      ct=1
    t-=1
   pt=0
   lst1.append(0)
   for i in lst0:
    for j in lst1:
     for k in lst1:
      if i==j^k:
       pt+=1
   if pt<len(lst0):
    wa+=1
  if wa==0:
   print(0)
  else:
   print(1)

Submission status: Time Limit Exceeded

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 slv(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 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 = 10
    #     A = [random.randint(1, 1<<4) for _ in range(N)]
    #     S = random.choices('01', k=N-1)
    #     S.append('0')

    #     # A = [2, 9, 6, 15, 7, 6, 9]
    #     # S = ['0', '1', '1', '1', '0', '0', '0']
    #     print(A)
    #     print(S)
    #     # a = slv(N, A, S)
    #     b = ref(N, A, S)
    #     if b == 0:
    #         break
    #     # if a != b:
    #     #     print(a, b)
    #     #     break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    t=int(input())
    for _ in range(t):
        st=time.time()
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                        break
                    if time.time()-st>0.02:
                        print(1)
                        ans=1
                        break
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
def main():
    t=int(input())
    for _ in range(t):
        st=time.time()
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                        break
                    if time.time()-st>30:
                        print(1)
                        ans=1
                        break
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

def judge(k ,si, x, alist):
  if si >= k - 1 :
    if x > 0 and x^alist[k-1] == 0:
      return 0
    elif x == 0 :
      return 0
    else:
      return 1
  ret = judge(k,si + 1,x,alist)
  ret1 = judge(k,si + 1,x^alist[si],alist)
  if ret != 0 or ret1 != 0:
    return 1
  return 0
  
for tc in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input()
  if s[-1] == '1':
    print(1)
  if s[-2:] == '00':
    print(0)
  else:
    print(judge(len(s),0,0,a))

Submission status: Time Limit Exceeded

Solution code:
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 = [0]
        p2 = [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: Time Limit Exceeded

Solution code:
t = int(input())


def xorset(l):
    s = set()
    for b in range(1 << len(l)):
        n = 0
        for i in range(0,len(l)):
            if b >> i & 1:
                n ^= l[i]
        s.add(n)
    return s


for _ in range(t):
    n = int(input())
    *a, = map(int,input().split())
    s = input()
    o = [a[i] for i in range(n) if s[i] == "1"]
    p = [a[i] for i in range(n) if s[i] == "0"]
    so = xorset(o)
    sp = xorset(p)
    if so - sp:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    t=int(input())
    for _ in range(t):
        ans=-1
        n=int(input())
        a=[int(j)for j in input().split()]
        s=input()
        if s[-1]=="1":
            ans=1
            print(ans)
        if ans==-1:
            lz=set()
            lo=set()
            for i,j in zip(a,s):
                if j=="1":
                    lo.add(i)
                    lz=set()
                else:
                    if i in lo:
                        lo.remove(i)
                    lz.add(i)
            cz=[0]*60
            for i in lz:
                for j in range(60):
                    cz[j]+=i>>j&1
            co=[0]*60
            for i in lo:
                for j in range(60):
                    co[j]+=i>>j&1
            for i,j in zip(cz,co):
                if i<j:
                    ans=1
                    print(1)
                    break
            if ans==-1:
                l=set()
                m=len(lz)
                lz=list(lz)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lz[j]
                    l.add(tmp)
                m=len(lo)
                lo=list(lo)
                for i in range(1<<m):
                    tmp=0
                    for j in range(m):
                        if i>>j&1:
                            tmp^=lo[j]
                    if tmp not in l:
                        ans=1
                        print(1)
                if ans==-1:
                    print(0)

if __name__ == '__main__':
    main()