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:
t=int(input())
res=list()

def ea(lst):
    flag=1
    while flag==1:
        flag=0
        for i in range(len(lst)):
            for j in range(i+1,len(lst)):
                if  lst[i]^lst[j] < lst[i] and lst[i]^lst[j]!=0:
                    flag=1
                    lst[i]=lst[i]^lst[j]
                elif lst[i]^lst[j] < lst[j] and lst[i]^lst[j]!=0:
                    flag=1
                    lst[j]=lst[i]^lst[j]
        z=0
        for i in range(len(lst)):
            for j in range(i+1,len(lst)):
                if z==0 and lst[i]==lst[j]:
                    lst.remove(lst[i])
                    z=1
                    
    return(lst)
        
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=str(input())
    black=list()
    white=list()
    for i in range(n):
        if s[i]=="1":
            black.append(a[i])
        else:
            white.append(a[i])
    black=ea(black)
    white=ea(white)
    black.extend(white)
    black=ea(black)
    ans=0
    for item in black:
        if not item in white:
            ans=1
    res.append(ans)
    
for i in res:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = map(int, args[i+1].split())
        S = map(int, tuple(args[i+2]))

        A0 = []
        A1 = []
        for a, s in zip(A, S):
            if s == 1:
                A0.append(a)
            elif s == 0:
                A1.append(a)

        X = set([0])
        for a in A1:
            for x in X.copy():
                X.add(a ^ x)

        Y = set([0])
        for a in A0:
            for y in Y.copy():
                Y.add(a ^ y)

        ret.append(0 if X <= Y else 1)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    t = int(sys.stdin.readline())

    for _ in range(t):
        n = int(sys.stdin.readline())
        a = list(map(int, sys.stdin.readline().split()))
        s = list(sys.stdin.readline())

        if s[-1] == 1:
            print(1)
            break

        que = [0]
        for i in range(n):
            tmp = set()
            t_add = tmp.add
            if s[i] == "1":
                for q in que:
                    if q == 0:
                        t_add(q ^ a[i])
                    elif q == a[i]:
                        t_add(q)
                    else:
                        t_add(q)
                        t_add(q ^ a[i])
            else:
                if a[i] in que or 0 in que:
                    t_add(0)
                else:
                    for q in que:
                        t_add(q)
                        t_add(q ^ a[i])

            que = tuple(tmp)

        if 0 in que:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
res=list()

def ea(lst):
    flag=1
    while flag==1:
        flag=0
        for i in range(len(lst)):
            for j in range(i+1,len(lst)):
                if  lst[i]^lst[j] < lst[i] and lst[i]^lst[j]!=0:
                    flag=1
                    lst[i]=lst[i]^lst[j]
                elif lst[i]^lst[j] < lst[j] and lst[i]^lst[j]!=0:
                    flag=1
                    lst[j]=lst[i]^lst[j]
    return(lst)
        
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=str(input())
    black=list()
    white=list()
    for i in range(n):
        if s[i]=="1":
            black.append(a[i])
        else:
            white.append(a[i])
            black.append(a[i])
    black=ea(black)
    white=ea(white)
    ans=0
    for item in black:
        if not item in white:
            ans=1
    res.append(ans)
    
for i in res:
    print(i)

Submission status: Time Limit Exceeded

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

        dp = [[0, 0] for i in range(N)]
        # 人１がビットを最後に立てた後に０にできるなら０にならない
        L = max(A).bit_length()

        ret = 0

        B = [A[i] for i in range(N) if S[i] == '0']
        C = [A[i] for i in range(N) if S[i] == '1']

        s1 = set([0])
        s0 = set([0])

        for x in B:
            tmp = set()
            for y in s0:
                tmp.add(y ^ x)
            s0 |= tmp

        for x in C:
            tmp = set()
            for y in s1:
                tmp.add(y ^ x)
            s1 |= tmp

        if len(s1 - s0) > 0:
            print(1)
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
n,a,s = [],[],[]
for i in range(t):
    n.append(int(input()))
    a.append([int(x) for x in input().split(' ')])
    s.append(input())

def ret_set(aa):
    aa = list(set(aa))
    l = len(aa)
    sets = {0}
    for j in range(l):
        buf = list(sets)
        for s in buf:
            sets.add(s ^ aa[j])
    return sets

for i in range(t):
    if s[i][-1] == '1':
        print(1)
    else:
        l = s[i].rfind('1')+1
        aa = a[i][:l]
        sets = ret_set(aa)
        aa = a[i][l:]
        zeros = ret_set(aa)
        if len(sets.difference(zeros)) == 0:
            print(0)
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
def listxor(a):
    count = [0] * (len(max(a))-2)
    
def checkxor(a,b):
    zero = set([0])
    for x in a:
        temp = set()
        for y in zero:
            temp.add(x^y)
        zero |= temp
    one = set([0])
    for x in b:
        temp = set()
        for y in one:
            c = x ^ y
            if c not in zero:
                return False
            else:
                temp.add(x^y)
        one |= temp
    return True

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1] == '1':
        print('1')
    elif S.count('0') == len(S):
        print('0')
    else:
        zeros = []
        ones = []
        for j in range(len(S)):
            if S[j] == '1':
                ones.append(A[j])
                current = 1
                break
        for k in range(j+1,len(S)):
            if S[k] == '1':
                if current == 1:
                    ones.append(A[k])
                else:
                    if checkxor(zeros,ones) == False:
                        print('1')
                        break
                    else:
                        ones.append(A[k])
                        current = 1
            else:
                if current == 0:
                    zeros.append(A[k])
                else:
                    zeros.append(A[k])
                    current = 0
        if checkxor(zeros,ones) == False:
            print('1')
        else:
            print('0')

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

xor_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):
      if not('0' in s[index-1:]):
        return r
    
    if(r == 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
    else:
      temp = case(r, n, a, s, index)
      if(temp != 0):
        temp = case(r, n, a, s, index)
  elif(s_case == '0'):
    
    if(r == 0):
      if not('1' in s[index-1:]):
        return 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)
    else:
      temp = case(r, n, a, s, index)
  return temp

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')
  else:
    print('1')
  result = 0

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()
    def backtrack(i,x):
        if i == N:
            return x==0
        if S[i] == '0':
            if backtrack(i+1,x^int(A[i])) == False and backtrack(i+1,x)==False:
                return False
            else:
            #if backtrack(i+1,x^int(A[i])) == True or backtrack(i+1,x)==True:
                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:
def resolve():
	# T: test case数
	T = int(input())

	# test caseの実行
	for _ in range(T):
		# N: round数
		N = int(input())
		# XORする数
		A = map(int, input().split())
		# 人0 or 1
		S = input()
		# 最後がプレーヤー１の場合
		if S[-1] == '1':
			print('1')
		else:
			# プレーヤー毎のxor結果のパターンを考える
			pattern1 = [0]
			pattern2 = [0]
			for a, s in zip(A, S):
				if s=='1':
					pattern1.extend(
						[x^a for x in pattern1]
					)
				else:
					pattern2.extend(
						[x^a for x in pattern2]
					)
			pattern1 = set( tuple( pattern1 ) )
			pattern2 = set( tuple( pattern2 ) )
			if len(pattern1 - pattern2) > 0:
				print('1')
			else:
				print('0')
                
resolve()

Submission status: Time Limit Exceeded

Solution code:
# copied from stackoverflow

def least_bit_set(x):
    return x & (-x)


def eliminate(values):
    values = list(values)
    i = 0
    while True:
        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, eliminated_values):
    for y in eliminated_values:
        if least_bit_set(y) & x != 0:
            x ^= y
    return x == 0


def play():
    n = int(input())
    a = list(map(int, input().split()))
    ss = input()
    s = [0]*n
    for i in range(0, n):
        if ss[i] == '1':
            s[i] = 1
    a = a[::-1]
    s = s[::-1]

    cur = []
    fl = True

    for i in range(0, n):
        if s[i] == 0:
            cur.append(a[i])
        else:
            values = cur
            eliminated_values = eliminate(values)
            if not in_span(a[i], eliminated_values):
                fl = False
                break

    if fl:
        print(0)
    else:
        print(1);

t = int(input())
while t > 0:
    t -= 1
    play()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

xor_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):
      if not('0' in s[index-1:]):
        return r
    
    if(r == 0):
      temp = r^a_case
      temp = case(temp, n, a, s, index)
    else:
      temp = case(r, n, a, s, index)
  elif(s_case == '0'):
    
    if(r == 0):
      if not('1' in s[index-1:]):
        return 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)
    else:
      temp = case(r, n, a, s, index)
  return temp

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')
  else:
    print('1')
  result = 0

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
ls = [input() for _ in range(t*3)]

for ti in range(t):
  n = int(ls[ti*3])
  a = list(map(int,ls[ti*3+1].split()))
  s = ls[ti*3+2]
  z = set()
  o = set()
  for i in range(n):
    if s[i] == "0" and s[i] not in z:
      tmp = z.copy()
      for e in tmp:
        z.add(a[i]^e)
      z.add(a[i])
      #print("z: {}".format(z))
    if s[i] == "1" and s[i] not in o:
      tmp = o.copy()
      for e in tmp:
        o.add(a[i]^e)
      o.add(a[i])
      #print("o: {}".format(o))
  #print(o)
  #print(z)
  #print(o <= z)
  if o<=z:
    print(0)
  else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    T = int(input())
    ans = []
    for _ in range(T):
        N = int(input())
        A = [int(x) for x in input().split()]
        S = [int(x) for x in list(input())]
        length = 0
        statuses = [0,0]
        status = 0
        # print('=======================')
        turn = 0
        while len(S) > 0:
            # 連続ターン数を数える
            turn_count = turn
            s = S[0]
            while len(S) > 0:
                _s = S[0]
                if s == _s:
                    S.pop(0)
                    turn_count += 1
                else:
                    break
            # 人が最適にxorした値を更新
            # print('###')
            # print(turn_count)
            for bit in range(1,2**(turn_count-turn)):
                turn_values = A[turn:turn_count]
                # print(bin(bit),turn_values)
                totalA = status
                for i,v in enumerate(turn_values):
                    if (1<<i) & bit:
                        totalA ^= v
                    # print((1<<i) & bit,totalA,v)
                # print(totalA)
                if s == 1 and status < totalA:
                    status = totalA
                elif s == 0 and status > totalA:
                    status = totalA
            # print(status)
            turn += turn_count
        ans.append(status)

    # print('############################')
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

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

    se0 = set([0])
    se1 = set([0])
    ans = 0
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            nxt = set()
            for k in se0:
                nxt.add(k)
                nxt.add(k^A[i])
            se0 = nxt
        else:
            nxt = set()
            for k in se1:
                nxt.add(k)
                nxt.add(k^A[i])
            se1 = nxt
        for k in se1:
            if k not in se0:
                ans = 1
                break
        if ans:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    ans = '0'
    for i in range(N):
        if S[i]=='1':
            l = []
            for j in range(i+1,N):
                if S[j]=='0':
                    l.append(A[j])
            cand = []
            for a in l:
                cand.append(a)
                for b in l:
                    cand.append(a^b)
            cand = list(set(cand))
            cand.sort()
            s = A[i]
            for a in cand:
                if s^a<s:
                    s ^= a
            for a in cand:
                if s^a<s:
                    s ^= a
            if s != 0:
                ans = '1'
                
    print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
# copied from stackoverflow

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, eliminated_values):
    for y in eliminated_values:
        if least_bit_set(y) & x != 0:
            x ^= y
    return x == 0


def play():
    n = int(input())
    a = list(map(int, input().split()))
    ss = input()
    s = [0]*n
    for i in range(0, n):
        if ss[i] == '1':
            s[i] = 1
    a = a[::-1]
    s = s[::-1]

    cur = []
    fl = True

    for i in range(0, n):
        if s[i] == 0:
            cur.append(a[i])
        else:
            values = cur
            eliminated_values = eliminate(values)
            if not in_span(a[i], eliminated_values):
                fl = False
                break

    if fl:
        print(0)
    else:
        print(1);

t = int(input())
while t > 0:
    t -= 1
    play()

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
res=list()
def su(i):
    i=bin(i)[2:]
    res=0
    for a in i:
        if a == "1":
            res+=1
    return(res)

def ea(lst):
    flag=1
    while flag==1:
        flag=0
        for i in range(len(lst)):
            for j in range(i+1,len(lst)):
                if  su(lst[i]^lst[j])< su(lst[i]):
                    flag=1
                    lst[i]=lst[i]^lst[j]
                elif su(lst[i]^lst[j]) < su(lst[j]):
                    flag=1
                    lst[j]=lst[i]^lst[j]
    return(lst)
        
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=str(input())
    black=list()
    white=list()
    for i in range(n):
        if s[i]=="1":
            black.append(a[i])
        else:
            white.append(a[i])
    black=ea(black)
    white=ea(white)
    ans=0
    for item in black:
        if not item in white:
            ans=1
    res.append(ans)
    
for i in res:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import chain, combinations
from functools import reduce


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

def xor(a, b):
    return a^b

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = list(map(int, str(input())))
    S1_A = list(set([A[i] for i, x in enumerate(S) if x == 1]))
    S0_A = list(set([A[i] for i, x in enumerate(S) if x == 0]))

    #print(S1_A, S0_A)
    #print(list(powerset(S1_A)))
    #print(list(powerset(S0_A)))
    
    cand0 = [0]
    cand1 = [0]
    for i in list(powerset(S1_A))[1:]:
        cand1.append(reduce(xor, i))

    for i in list(powerset(S0_A))[1:]:
        cand0.append(reduce(xor, i))

    #print(set(cand1), set(cand0))

    if set(cand0) == set(cand1):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

Solution code:
t = int(input())
n,a,s = [],[],[]
for i in range(t):
    n.append(int(input()))
    a.append([int(x) for x in input().split(' ')])
    s.append(input())

def ret_set(aa):
    sets = {0}
    for j in range(len(aa)):
        buf = set()
        for s in sets:
            buf.add(s ^ aa[j])
        sets |= buf
    return sets

for i in range(t):
    if s[i][-1] == '1':
        print(1)
    else:
        l = s[i].rfind('1')+1
        aa = a[i][:l]
        sets = ret_set(aa)
        aaa = a[i][l:]
        zeros = ret_set(aaa)
        if len(sets.difference(zeros)) == 0:
            print(0)
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

    T=int(input())
    for t in range(T):
        N=int(input())
        A=list(map(int, input().split()))
        S=list(input())
        # print(A)
        # print(S)
        S0=[]
        S1=[]
        for i in range(N):
            if S[i]=='0':
                S0.append(A[i])
            else:
                S1.append(A[i])

        p0=set()
        p1=set()
        for i in range(len(S0)):
            for tmp in itertools.combinations(S0,i+1):
                x=tmp[0]
                for j in range(1,len(tmp)):
                    x=x^tmp[j]
                p0.add(x)

        for i in range(len(S1)):
            for tmp in itertools.combinations(S1,i+1):
                x=tmp[0]
                for j in range(1,len(tmp)):
                    x=x^tmp[j]
                p1.add(x)

        if p1<=p0:
            print(0)
        else:
            print(1)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

t = int(input())

for i in range(t):
    n = int(input())
    a = []
    a = list(map(int,input().split()))
    s = input()
    sl = len(s)
    
    if s[sl-1] == '1':
#        print("saisyo")
        print(1)
    else:
        
        for i in range(1,2**sl):  # 空集合を除く場合はrange(1, 2**len(list1))
            list2 = []
            x = 0
            # 処理対象の数字を2進数に変換し、各桁のbitが１かどうかを判断する
            for j in range(sl):
#                print(s[j:sl])
    	        # 演算結果が1なら処理を行う
                if x == 0 and int(s[j:sl]) == 0:
#                    print(j,s[j:sl])
                    break
                elif (i >> j) &1 == 1 or (s[j] == '1'):
                    if (s[j] == '1') or(s[j] == '0' and x != 0):
                        x = x^a[j]
#                            print(str(i) + ':' + str(x))
                
            if x == 0:
                print(0)
                break
        else:
            print(1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

t = int(input())

ans = []
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = list(map(int, input().rstrip()))
    if s[-1] == 1:
        ans.append(1)
        continue
    elif s.count(1) == 0:
        ans.append(0)
        continue
    a0 = []
    a1 = []
    for i in range(n):
        if s[i] == 0:
            a0.append(a[i])
        else:
            a1.append(a[i])

    arr0 = []
    arr1 = []
    for i in range(2, len(a0) + 1):
        tmp = combinations(a0, i)
        for j in tmp:
            tmp_xxx = 0
            for k in j:
                tmp_xxx ^= k
            arr0.append(tmp_xxx)
    arr0 = set(arr0 + a0)

    for i in range(2, len(a1) + 1):
        tmp = combinations(a1, i)
        for j in tmp:
            tmp_xxx = 0
            for k in j:
                tmp_xxx ^= k
            arr1.append(tmp_xxx)
    arr1 = set(arr1 + a1)

    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:

import itertools
import math

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))


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 = []
    zero = []
    for i in range(n[ti]):
        if people[i] == 1:
            one.append(xor_number[i])
        if people[i] == 0:
            zero.append(xor_number[i])
    #make max in one
    comb = powerset(one)
    max_one = -math.inf
    for c in comb:
        x = 0
        for i in c:
            x ^= i
        if max_one < x:
            max_one = x
    
    ans = False
    comb = powerset(zero)
    target = max_one
    for c in comb:
        x = 0
        for i in c:
            x ^= i
        if x == target:
            ans = True
            break
    if ans:
        print(0)
    else: 
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

for i in range(int(input())):
    
    handan=[]
    kai = int(input())
    kazu = [int(j) for j in input().split()]
    input()
    for j in itertools.product("YN",repeat = kai):
        x = 0
        for yousuu,k in enumerate(j):
            if k == "Y":
                x ^= kazu[yousuu]
        
        handan.append(x)
        if handan.count(0) == 2:
            break
        
    if handan.count(0) >= 2:
        print("0")
    else:
        print("1")

Submission status: Time Limit Exceeded

Solution code:
import itertools

for i in range(int(input())):
    
    handan=[]
    kai = int(input())
    kazu = [int(j) for j in input().split()]
    input()
    for j in itertools.product("YN",repeat = kai):
        x = 0
        for yousuu,k in enumerate(j):
            if k == "Y":
                x ^= kazu[yousuu]
                 
        handan.append(x)
        
    if handan.count(0) >= 2:
        print("0")
    else:
        print("1")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Helper:
    def __init__(self):
        self.pat = set()

    def patterns(self, cur: int, candidates: list):
        if not candidates:
            self.pat.add(cur)
            return
        else:
            self.pat.add(cur ^ candidates[0])
            self.pat.add(cur)
            self.patterns(cur ^ candidates[0], candidates[1:])
            self.patterns(cur, candidates[1:])


def main():
    T = int(input().strip())
    testcases = []
    ans = [0] * T
    for j in range(T):
        case = dict()
        case["rounds"] = int(input().strip())
        xor_num = [int(i) for i in input().strip().split()]
        turn = input().strip()
        case["0"] = list()
        case["1"] = list()
        for i, p in enumerate(list(turn)):
            case[p].append(xor_num[i])

        p0 = Helper()
        p0.patterns(0, case["0"])
        p1 = Helper()
        p1.patterns(0, case["1"])

        for candidate in list(p1.pat):
            if candidate not in p0.pat:
                ans[j] = 1

    return ans


if __name__ == "__main__":
    for ans in main():
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

T = int(input())


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    S = list(input())

    while S[-1] == "1" and A[-1] == 0:
        S.pop()
        A.pop()
        N -= 1

    if N == 0:
        return 0

    if S[-1] == "1":
        return 1

    candidate = [set([0]) for _ in range(2)]

    OK = True
    for i in range(N)[::-1]:
        a = A[i]
        s = int(S[i])

        nxt = []
        for x in list(candidate[0]):
            nxt.append(x)
            nxt.append(x ^ a)

        candidate[s] = set(nxt)

        if s == 1:
            zero = candidate[0]
            one = candidate[1]

            if one <= zero:
                pass
            else:
                OK = False
                break

    ans = 1

    if OK:
        ans = 0

    return ans


ANS = []
for _ in range(T):
    t = solve()
    ANS.append(t)

print("\n".join(map(str, ANS)))