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:
def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i+1]:
                for v in dp[i+1]:
                    dp[i].add(v)
    if 0 in dp[0]:
        return 0
    else:
        return 1

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = [set() for _ in range(N+1)]
    dp[N].add(0)
    for i in reversed(range(N)):
        if S[i] == "0":
            for v in dp[i+1]:
                dp[i].add(v)
                dp[i].add(v ^ A[i])
        else:
            for v in dp[i+1]:
                if v ^ A[i] in dp[i+1]:
                    dp[i].add(v)
    if 0 in dp[0]:
        return 0
    else:
        return 1

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    DP = [set() for _ in range(N+1)]
    DP[N].add(0)
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            for x in DP[i+1]:
                DP[i].add(x)
                DP[i].add(x ^ A[i])
        else:
            if A[i] in DP[i+1]:
                for x in DP[i+1]:
                    DP[i].add(x)

    if 0 in DP[0]:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
def gauss_jordan(A):
  m=len(A)
  n=len(A[0])
  rank=0
  for col in range(n):
    pivot=-1
    for row in range(rank,m):
      if A[row][col]!=0:
        pivot=row
        break
    if pivot==-1:
      continue
    A[pivot],A[rank]=A[rank],A[pivot]
    for row in range(m):
      if row!=rank and A[row][col]!=0:
        for col2 in range(n):
          A[row][col2]^=A[rank][col2]      
    rank+=1
  if rank==len(A):
    return True
  else:
    return False

def make_vector(val):
  ret=[]
  for i in range(60,-1,-1):
    if val&(1<<i):
      ret.append(1)
    else:
      ret.append(0)
  return ret

t=int(input())
for _ in range(t):
  n=int(input())
  arr=list(map(int,input().split()))
  s=input()
  if s[-1]=='1':
    print(1)
    continue
  A=[make_vector(arr[-1])]
  for i in range(n-2,-1,-1):
    vector=make_vector(arr[i])
    if gauss_jordan(A+[vector]):
      if s[i]=='1':
        print(1)
        break
      if s[i]=='0':
        A.append(vector)
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

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


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

    print("0")

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

Submission status: Time Limit Exceeded

Solution code:

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

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

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

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

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

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

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

    print("0")

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

Submission status: Time Limit Exceeded

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 = [0]

    for i in range(N-1, -1, -1):
        #print(i, dp)
        if S[i] == "0":
            dp += [x^A[i] for x in dp if x^A[i] not in dp]

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

    print("0")

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

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

# 逆から、人1が多かったらその時点で駄目、人0が人1の数を覆い尽くす必要がある
T = ir()

def solve():
    N = ir()
    A = lr()
    S = sr()
    dp = [None] * (N+1)
    dp[N] = {0}
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            dp[i] = dp[i+1].copy()
            for element in dp[i+1]:
                dp[i].add(element ^ A[i])
        elif S[i] == '1':
            if A[i] not in dp[i+1]:
                return 1
            else:
                dp[i] = dp[i+1]
    return 0
    
for _ in range(T):
    print(solve())

Submission status: Time Limit Exceeded

Solution code:





# numss = [[] for i in range(n+1)]
# def f(num,pos):
# 	if pos == n+1:
# 		return
# 	numss[pos].append(num)
# 	f(num,pos+1)
# 	if pos < n:
# 		f(num^a[pos],pos+1)

# f(0,0)


# i = 0
# for nums in numss:
# 	if i < n:
# 		print("{},{}: ".format(s[i],a[i]),end="")
# 	else:
# 		print("     ",end="")
# 	for num in nums:
# 		print("{num:^{w}}".format(num=num,w=2**(n+1-i)),end='')
# 	print()
# 	i += 1


def f():
	n = int(input())
	a = list(map(int,input().split()))+[]
	s = input()
	dp = [0]
	for i in reversed(range(n)):
		# print(i,dp)
		if s[i] == '0':
			dp = dp + [v^a[i] for v in dp]
		else:
			if not a[i] in dp:
				dp = []
	# print(dp)
	if dp == []:
		print(1)
	else:
		print(0)


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

Submission status: Time Limit Exceeded

Solution code:
def examA():
    T = I()
    ans = [1]*T
    for t in range(T):
        N = I()
        A = LI()
        S = SI()
        dp = [set()for _ in range(N+1)]
        dp[N].add(0)
        if S[-1]=="1":
            ans[t] = 1
            continue

        def judge():
            i = N
            for s in S[::-1]:
                #print(s, i)
                i -= 1
                a = A[i]
                dp[i] = deepcopy(dp[i + 1])
                if s == "0":
                    for d in dp[i + 1]:
                        dp[i].add(d ^ a)
                else:
                    if a in dp[i + 1]:
                        continue
                    ans[t] = 1
                    return
            if 0 in dp[0]:
                ans[t] = 0
            return
        judge()
    for v in ans:
        print(v)
    return

def examB():
    S = SI()
    N = len(S)
    sub_ = defaultdict(int)
    cur = 0
    keep = 0
    for i,s in enumerate(S):
        if s=="?":
            if cur==0:
                keep = i
            cur += 1
        else:
            if cur>0:
                sub_[keep] = cur%2
                sub_[i-1] = cur % 2
            cur = 0
    flag = True
    for i,s in enumerate(S):
        if i%2==0:
            if s=="1":
                flag = False
                break
        else:
            if s=="0":
                flag = False
                break
    if flag:
        print(1)
        return
    flag = True
    for i,s in enumerate(S):
        if i%2==1:
            if s=="1":
                flag = False
                break
        else:
            if s=="0":
                flag = False
                break
    if flag:
        print(1)
        return
    ans = 2
    cur = 0
    cur0 = [0]*N
    for i,s in enumerate(S):
        if s=="0":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
        cur0[i] = cur
    cur = 0
    cur1 = [0]*N
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
        cur1[i] = cur
    cur = 0
    for i,s in enumerate(S[:-1]):
        if s=="0":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur
    cur = 0
    for i,s in enumerate(S[::-1]):
        if s=="1":
            cur += 1
        else:
            cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans = cur

    max0 = set()
    for i,s in enumerate(S[1:],1):
        if s == "?" and cur0[i-1] == ans:
            max0.add(i)

    max1 = set()
    for i,s in enumerate(S[1:],1):
        if s == "?" and cur1[i-1] == ans:
            max1.add(i)
    #print(cur0)
    #print(cur1)
    #print(max1)

    cur = 0
    ne = 0
    for i,s in enumerate(S):
        #print(cur)
        if s=="0":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max1:
                #print(i,s,sub_)
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    ne = 0
    cur = 0
    for i,s in enumerate(S):
        if s=="1":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max0:
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return

    cur = 0
    ne = 0
    for i,s in enumerate(S[::-1]):
        #print(cur)
        if s=="0":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max1:
                #print(i,s,sub_)
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    ne = 0
    cur = 0
    for i,s in enumerate(S[::-1]):
        if s=="1":
            cur += 1
            if ne>0:
                cur += 1
                ne = 0
        else:
            if s=="?" and i in max0:
                cur += 1
                if sub_[i]==1:
                    ne = 1
            else:
                cur -= 1
            if cur<0:
                cur = 0
        if ans<cur:
            ans += 1
            print(ans)
            return
    print(ans)
    return

def examC():
    N, A, B = LI()

    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examA()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn

111??000
111?000
11??11
11???00
"""

Submission status: Time Limit Exceeded

Solution code:

v=set()

def make_possible(n):
    # orig=set(v)

    for i in list(v):
        v.add(n^i)

    v.add(n)

    return



T=int(input())

ans=[0 for i in range(T)]

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

    if S[N-1] == '1':
        ans[i]=1
        next
    
    if Sinput == '0'*N :
        ans[i]=0
        next
    
    v.clear()
    v.add(0)
    for j in range(N-1,-1,-1):
        # print("j=",j)
        # print(A[j],v, (not (A[j] in v)))
        if S[j]=='1' and (not (A[j] in v)):
            ans[i]=1
            # print("1 win!")
            break
        else:
            make_possible(A[j]) # update v
        
        # print(v)

for i in range(T):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:


def make_possible(n,B):
    ans1=set(B)

    for i in B:
        ans1.add(n)
        ans1.add(n^i)

    return ans1



T=int(input())

ans=[0 for i in range(T)]

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

    if S[N-1] == '1':
        ans[i]=1
        next
    
    if Sinput == '0'*N :
        ans[i]=0
        next
    
    v=set()
    v.add(0)
    for j in range(N-1,-1,-1):
        # print("j=",j)
        # print(A[j],v, (not (A[j] in v)))
        if S[j]=='1' and (not (A[j] in v)):
            ans[i]=1
            # print("1 win!")
            break
        else:
            v=make_possible(A[j],v)
        
        # print(v)

for i in range(T):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=input()
    dp={}
    def solve(a,i):
        if (a,i) in dp:
            return dp[(a,i)]
        if i==n-1:
            if s[i]=='0':
                if a==0 or a^l[i]==0:
                    return 0
                else:
                    return 1
            else:
                if a!=0 or a^l[i]!=0:
                    return 1
                else:
                    return 0
        if s[i]=='1':
            if solve(a,i+1) or solve(a^l[i],i+1):
                dp[(a,i)]=1
            else:
                dp[(a,i)]=0
        else:
            if solve(a,i+1)==0 or solve(a^l[i],i+1)==0:
                dp[(a,i)]=0
            else:
                dp[(a,i)]=1
        return dp[(a,i)]

    print(solve(0,0))

Submission status: Time Limit Exceeded

Solution code:
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=input()

    def solve(a,i):
        if i==n-1:
            if s[i]=='0':
                if a==0 or a^l[i]==0:
                    return 0
                else:
                    return 1
            else:
                if a!=0 or a^l[i]!=0:
                    return 1
                else:
                    return 0
        if s[i]=='1':
            if solve(a,i+1) or solve(a^l[i],i+1):
                return 1
            else:
                return 0
        else:
            if solve(a,i+1)==0 or solve(a^l[i],i+1)==0:
                return 0
            else:
                return 1
    
    print(solve(0,0))

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

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

    sa = set()
    for i, ss in enumerate(s):
        if ss == '1':
            sa.add(a[i])

    a = a[::-1]
    s = s[::-1]

    m = {0}
    for i in range(n):
        ss = s[i]
        aa = a[i]
        if ss == '0':
            ma = {mm^aa for mm in m}
            sa = sa - ma
            if len(sa) == 0:
                out.append(0)
                break
            m.update(ma)
        else:
            if aa not in m:
                out.append(1)
                break
    else:
        out.append(0)

for o in out:
    print(o)

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

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

    a = a[::-1]
    s = s[::-1]

    m = {0}
    for i in range(n):
        ss = s[i]
        aa = a[i]
        if ss == '0':
            m.update({mm^aa for mm in m})
        else:
            if not aa in m:
                out.append(1)
                break
    else:
        out.append(0)

for o in out:
    print(o)

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

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

    a = a[::-1]
    s = s[::-1]

    m = {0}
    for i in range(n):
        ss = s[i]
        aa = a[i]
        if ss == '0':
            m.update({mm^aa for mm in m})
        else:
            if len({mm^aa for mm in m} & m) == 0:
                out.append(1)
                break
    else:
        out.append(0)

for o in out:
    print(o)

Submission status: Time Limit Exceeded

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(int(0))
    for i in range(n[ti]-1,-1,-1):
        if people[i] == 1:
            if (xor_number[i] in dp[i+1]) == True:
                dp[i] = dp[i+1]
            else:
                dp[0] = None
                break
        if people[i] == 0:
            dp[i] = dp[i+1].copy()
            new = set()
            for j in dp[i]:
                new.add(int(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: Time Limit Exceeded

Solution code:
import itertools
import math
import bisect

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])))
    one = set()
    zero = set()
    for i in range(n[ti]):
        if people[i] == 1:
            one.add(xor_number[i])
            new = set()
            for j in one:
                new.add(xor_number[i] ^ j )
            one = one.union(new)
        if people[i] == 0:
            zero.add(xor_number[i])
            new = set()
            for j in zero:
                new.add(xor_number[i] ^ j )    
            zero = zero.union(new)
    #make max in one
    if len(one - zero) == 0:
        print(0)
    else: 
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from 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: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  for orders in range(n-1,-1,-1):
    man = s[orders]
    amn = a[orders]
    if man=="0":
      man0winset = man0winset | set(map(lambda x:x^amn, 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,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  start=True
  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 | set(map(lambda x:x^amn, man0winset))
    else:
      if amn not in man0winset:
        man0winset=set([])
      #man0winset = man0winset & set(map(lambda x:x^amn, man0winset))
  if 0 in man0winset:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  start=True
  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 | set(map(lambda x:x^amn, man0winset))
    else:
      man0winset = man0winset & set(map(lambda x:x^amn, man0winset))
  if 0 in man0winset:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  start=True
  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:
      man0winset = man0winset & {x^amn for x in man0winset}
  if 0 in man0winset:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  start=True
  if s[-1]=="1":
    print(1)
    return
  for orders in range(n-1,-1,-1):
    man = s[orders]
    amn = a[orders]
    if man=="0":
      man0winset = man0winset | set([x^amn for x in man0winset])
    else:
      man0winset = man0winset & set([x^amn for x in man0winset])
  if 0 in man0winset:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
def main(n,a,s):
  man0winset=set([0])
  start=True
  for orders in range(n-1,-1,-1):
    man = s[orders]
    amn = a[orders]
    if  amn == 0:
       continue
    if man=="0":
      man0winset = man0winset | set([x^amn for x in man0winset])
    else:
      man0winset = man0winset & set([x^amn for x in man0winset])
  if 0 in man0winset:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

for _ in [0]*T:
    N = int(input())
    *A, = map(int,input().split())
    S = input()

    B = []
    ans = 0
    for s,a in zip(S[::-1],A[::-1]):
        if s=="0":
            B.append(a)
        else:
            # check
            C = B[:]
            for i in range(64):
                for b in C:
                    if (b >> i) & 1 == 1: break
                else:
                    continue
                if (a >> i) & 1 == 1: a ^= b
                for j,c in enumerate(C):
                    if (c >> i) & 1 == 1: C[j] ^= b
            if a!=0:
                ans = 1
                break
    print(ans)