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:
# 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 = [set()] * (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])
        else:
            cand = dp[i+1].copy()
            cand2 = set()
            for element in dp[i+1]:
                cand2.add(element ^ A[i])
            dp[i] = cand.intersection(cand2)
            if 0 not in dp[i]:
                print(1); return
    print(0); return
    
for _ in range(T):
    solve()

Submission status: Time Limit Exceeded

Solution code:
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

    dp = [set() for x in range(n + 1)]
    dp[0].add(0)

    for i in range(n):
        for x in list(dp[i]):
            tmp = x ^ a[i]
            dp[i + 1].add(tmp)
        for x in list(dp[i]):
            dp[i + 1].add(x)
        if s[i] == 1 and 0 in dp[i + 1]:
            dp[i + 1].remove(0)

    if 0 in dp[-1]:
        ans.append(0)
    else:
        ans.append(1)

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

    dp = [set()]

    dp = [set() for x in range(n + 1)]
    dp[0].add(0)

    for i in range(n):
        for x in list(dp[i]):
            tmp = x ^ a[i]
            dp[i + 1].add(tmp)
        for x in list(dp[i]):
            dp[i + 1].add(x)
        if s[i] == 1 and 0 in dp[i + 1]:
            dp[i + 1].remove(0)

    if 0 in dp[-1]:
        ans.append(0)
    else:
        ans.append(1)

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

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = [set()]*(N + 1)
    dp[0].add(0)
    for i in range(0, len(A)):
        if S[i] == '1':
            if A[i] in dp[i]:
                dp[i+1] = dp[i]
            else:
                dp[i+1] = set()
        else:
            dp[i+1] |= dp[i]
            dp_list = list(dp[i])
            for j in range(len(dp_list)):
                dp[i+1].add(dp_list[j] ^ A[i])
    return dp[N] == set()

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

Submission status: Time Limit Exceeded

Solution code:
def solve(N, A, S):
    dp = [[]]*(N + 1)
    dp[0].append(0)
    for i in range(0, len(A)):
        if S[i] == '1':
            if A[i] in dp[i]:
                dp[i+1] = dp[i]
            else:
                dp[i+1] = []
        else:
            dp[i+1].extend(dp[i])
            for j in range(len(dp[i])):
                dp[i+1].append(dp[i][j] ^ A[i])
    return dp[N] == []

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

Submission status: Time Limit Exceeded

Solution code:
def get_operation_list(n):
    operation_list = []
    for i in range(2 ** n):
        operation = []
        for j in range(n):
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                operation.append(True)
            else:
                operation.append(False)
        operation_list.append(operation)
    operation_list = sorted(operation_list, reverse=True)
    return operation_list
 
def get_pre_last(s):
    last_idx_s0 = [i for i, x in enumerate(s) if x == '0'][-1]
    last_idx_s1 = [i for i, x in enumerate(s) if x == '1'][-1]
    if last_idx_s0 < last_idx_s1:
        pre_last_idx = last_idx_s0
        pre_last_player = 's0'
    else:
        pre_last_idx = last_idx_s1
        pre_last_player = 's1'
    
    return pre_last_idx, pre_last_player
  
 
def get_x_list(operation_list, pre_last_player, pre_last_idx):
    x_list = []
    for operation in operation_list:
        x = 0
        for i, ope in enumerate(operation):
            if ope:
                x = x ^ an[i]
            # s0の最後のアクションで0以外(=最適な行動でないもの)は除外
            if pre_last_player == 's0' and pre_last_idx == i and x != 0:
                x = -1
                break
            # s1の最後のアクションで0(=最適な行動でないもの)は除外
            if pre_last_player == 's1' and pre_last_idx == i and x == 0:
                x = -1
                break
        if x != -1:
            x_list.append([operation, x])
    return x_list
 
def get_check_list(pre_last_player, x_list):
    pre = -1
    if pre_last_player == 's0':
        lose_xor = 1
    if pre_last_player == 's1' :
        lose_xor = 0
 
    pre_group = -1
    check_list = {}
    for x in x_list:
        group = x[2]
 
        if pre_group == -1:
            is_lose = False
        elif pre_group != group:
            check_list[group] = is_lose
            is_lose = False
 
        if x[1] == lose_xor:
            is_lose = True
        pre_group = group
    else:
        check_list[group] = is_lose
 
    return check_list
 
t = int(input())
 
result_list = []
 
for tn in range(t):
    n = int(input())
    an = list(map(int, input().split()))
    s = input()
 
    operation_list = get_operation_list(n)    
    pre_last_idx, pre_last_player = get_pre_last(s)
    x_list = get_x_list(operation_list, pre_last_player, pre_last_idx)
    for x in x_list:
        x.append(''.join(map(str, x[0][:pre_last_idx+1])))
    check_list = get_check_list(pre_last_player, x_list)
 
    if (len(check_list) == sum(check_list.values())) and pre_last_player == 's0':
        result_list.append(1)
    elif (len(check_list) != sum(check_list.values())) and pre_last_player == 's0':
        result_list.append(0)
    elif (len(check_list) == sum(check_list.values())) and pre_last_player == 's1':
        result_list.append(0)
    elif (len(check_list) != sum(check_list.values())) and pre_last_player == 's1':
        result_list.append(1)
 
for result in result_list:
    print(result)

Submission status: Time Limit Exceeded

Solution code:
def get_operation_list(n):
    operation_list = []
    for i in range(2 ** n):
        operation = []
        for j in range(n):
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                operation.append(True)
            else:
                operation.append(False)
        operation_list.append(operation)
    operation_list = sorted(operation_list, reverse=True)
    return operation_list

def get_pre_last(s):
    last_idx_s0 = [i for i, x in enumerate(s) if x == '0'][-1]
    last_idx_s1 = [i for i, x in enumerate(s) if x == '1'][-1]
    if last_idx_s0 < last_idx_s1:
        pre_last_idx = last_idx_s0
        pre_last_player = 's0'
    else:
        pre_last_idx = last_idx_s1
        pre_last_player = 's1'
    
    return pre_last_idx, pre_last_player
  

def get_x_list(operation_list, pre_last_player, pre_last_idx):
    x_list = []
    for operation in operation_list:
        x = 0
        for i, ope in enumerate(operation):
            if ope:
                x = x ^ an[i]
            # s0の最後のアクションで0以外(=最適な行動でないもの)は除外
            if pre_last_player == 's0' and pre_last_idx == i and x != 0:
                x = -1
                break
            # s1の最後のアクションで0(=最適な行動でないもの)は除外
            if pre_last_player == 's1' and pre_last_idx == i and x == 0:
                x = -1
                break
        if x != -1:
            x_list.append([operation, x])
    return x_list

def get_check_list(pre_last_player, x_list):
    pre = -1
    if pre_last_player == 's0':
        lose_xor = 1
    if pre_last_player == 's1' :
        lose_xor = 0

    pre_group = -1
    check_list = {}
    for x in x_list:
        group = x[2]

        if pre_group == -1:
            is_lose = False
        elif pre_group != group:
            check_list[group] = is_lose
            is_lose = False

        if x[1] == lose_xor:
            is_lose = True
        pre_group = group
    else:
        check_list[group] = is_lose

    return check_list

t = int(input())

result_list = []

for tn in range(t):
    n = int(input())
    an = list(map(int, input().split()))
    s = input()

    operation_list = get_operation_list(n)    
    pre_last_idx, pre_last_player = get_pre_last(s)
    x_list = get_x_list(operation_list, pre_last_player, pre_last_idx)
    for x in x_list:
        x.append(''.join(map(str, x[0][:pre_last_idx+1])))
    check_list = get_check_list(pre_last_player, x_list)

    if (len(check_list) == sum(check_list.values())) and pre_last_player == 's0':
        result_list.append(1)
    elif (len(check_list) != sum(check_list.values())) and pre_last_player == 's0':
        result_list.append(0)
    elif (len(check_list) == sum(check_list.values())) and pre_last_player == 's1':
        result_list.append(0)
    elif (len(check_list) != sum(check_list.values())) and pre_last_player == 's1':
        result_list.append(1)

for result in result_list:
    print(result)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    dp = set([0])
    for i in range(N-1,-1,-1):
        if S[i]=='0':
            add = set()
            for a in dp:
                add.add(a^A[i])
            dp |= add
        else:
            if A[i] not in dp:
                dp = set()
    if len(dp) != 0:
        ans = '0'
    else:
        ans = '1'
    print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
for h in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    l = [0]
    cmp = 0
    for i in range(1,n+1):
        if(s[-i] == '0'):
            for j in range(len(l)):
                l.append(l[j]^a[-i])
        else:
            if(not(a[-i] in l)):
                cmp = 1
                break
        #print(l)
    print(cmp)

Submission status: Time Limit Exceeded

Solution code:
def main(N, A, s):
    # 最終的にいくつになるかの組み合わせ(rootのindexの２進数が経路(1:する, 0:しない))
    root=[]
    for i in range(int('1'*N, 2)+1):
        x=0
        one = [n[0] for n in enumerate(format(i, '0'+str(N)+'b')) if n[1] == '1']
        if one != []:
            for j in one:
                x ^= A[j]
        root.append(x)

    # 連続出現回数で圧縮
    junn = []
    j=[s[0],0]
    for i in range(len(s)-1):
        j[1] += 1
        if s[i] != s[i+1]:
            junn.append(j)
            j = [s[i+1],0]
    junn.append(j)


    for j in junn:
        n = 2**j[1]
        a = len(root)//n
        root = [root[a*x:a*(x+1)] for x in range(n)]
        c = [r.count(0) for r in root]
        if j[0] == '1':
            root = root[c.index(min(c))]
        else:
            root = root[c.index(max(c))]
        if all(root):
            return 1
            
        elif not any(root):
            return 0
        
    if j[0] == '0':
        if 0 in root:
            return 0
        return 1
    else:
        if any(root):
            return 1
        return 0

T = int(input())
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  s = input()
  print(main(N, A, s))

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
for h in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    l = [0]
    cmp = 0
    for i in range(1,n+1):
        if(s[-i] == '0'):
            for j in range(len(l)):
                if(not(l[j]^a[-i] in l)):
                    l.append(l[j]^a[-i])
        else:
            if(not(a[-i] in l)):
                cmp = 1
                break
        #print(l)
    print(cmp)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
def solve():
    n=int(input())
    a=[int(_) for _ in input().split()]
    s=input()
    t0=[[0 for i in range(60)]for j in range(60)]
    t1=[[0 for i in range(60)]for j in range(60)]
    for i in reversed(range(n)):
        _s=bin(a[i])[2:]
        _s="0"*(60-len(_s))+_s
        if s[i]=='0':
            for j in range(60):
                for k in range(j,60):
                    if _s[j] != _s[k]:
                        t0[j][k]=2
                    elif _s[j]=='1':
                        t0[j][k]=max(1,t0[j][k])
                        
        else:
            for j in range(60):
                for k in range(j,60):
                    if _s[j] != _s[k]:
                        t1[j][k]=2
                        if t1[j][k]>t0[j][k]:
                          #  print(t1[j][k],t0[j][k],j,k,_s[j],_s[k],_s)
                            return '1'
                        
                    elif _s[j]=='1':
                        t1[j][k]=max(1,t0[j][k])
                        if t1[j][k]>t0[j][k]:
                            return '1'
        #print(_s,s[i])
    return '0'

for _ in range(t):
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    ans = True
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(reversed(S)):
        #print(L0, A[N - i - 1])
        if s == "0":
            tmp = set(np.array(L0) ^ A[N - i - 1])
            L0 = list(set(L0).union(tmp))
        if s == "1":
            if A[N - i - 1] not in L0:
                ans = False
                break

    print(int(not ans))

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 = [set() for i in range(N+1)]
        # 人１がビットを最後に立てた後に０にできるなら０にならない
        L = max(A).bit_length()
        dp[-1].add(0)
        for i in range(N-1, -1, -1):
            k = int(S[i])
            # print(A[i], dp[i+1], k)
            if k:
                if A[i] in dp[i+1]:
                    dp[i] = dp[i+1]

                else:
                    break
            else:
                dp[i] |= dp[i+1]
                for x in dp[i+1]:
                    dp[i].add(x ^ A[i])
        # print(dp)
        if len(dp[0]) > 0:
            print(0)
        else:
            print(1)
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 i in range(N+1)]
    # 人１がビットを最後に立てた後に０にできるなら０にならない
    L = max(A).bit_length()
    dp[-1].add(0)
    for i in range(N-1, -1, -1):
        k = int(S[i])
        # print(A[i], dp[i+1], k)
        if k:
            if A[i] in dp[i+1]:
                dp[i] = dp[i+1]

            else:
                break
        else:
            dp[i] |= dp[i+1]
            for x in dp[i+1]:
                dp[i].add(x ^ A[i])
    # print(dp)
    if len(dp[0]) > 0:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def f(a, s, n):
    if s[-1] == "1":
        return 1

    st = {0,}
    for i in range(n-1, -1, -1):
        ai, si = a[i], s[i]

        if si == "0":
            tmp = [ai ^x for x in st]
            st.update(tmp)
        else:
            if ai in  st:
                st.remove(ai)
            else:
                return 1
    return 0


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

    ans = []
    for i in range(T):
        N = int(input())
        A = list(iim())
        S  = input()

        ans.append(f(A, S, N))

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

if __name__ == "__main__":
    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 = []
    p = []
    for i in range(n):
        if s[i] == "1":
            o.append(a[i])
        else:
            p.append(a[i])
    so = set(o)
    sp = xorset(p)
    if so & sp == so:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = {0}
        for i in reversed(range(N)):
            if S[i] == "0":
                new = set()
                for k in used:
                    new |= {k ^ A[i]}
                used |= new
            else:
                if A[i] not in used: 
                    Ans[t] = 1
                    break
                
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections

T = int(input())
for i in range(T):
    x = 0
    L0 = [0]
    L1 = [0]
    #print("x:", x)
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    for i, s in enumerate(S):
        if s == "0":
            tmp = set(np.array(L0) ^ A[i])
            L0 = list(set(L0).union(tmp))
        if s == "1":
            tmp = set(np.array(L1) ^ A[i])
            L1 = list(set(L1).union(tmp))

    #print(L0, L1, set(L0) <= set(L1))
    if set(L0) <= set(L1):
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

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



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

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                task = task | set(q)
                task = standard_form(np.array(list(task), np.int64))
                task = set(task)
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                q = set(q) | task
                q = set(standard_form(np.array(list(q), np.int64)))
                if task != task | q:
                    win = "1"
                    break

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

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

    print(win)

Submission status: Time Limit Exceeded

Solution code:
import sys

t = int(input())
args = sys.stdin.readlines()

def judge(k ,si, x, alist):
  if si >= k - 1 :
    if (x > 0 and x^alist[k-1] == 0 )or 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(args[tc*3].replace('\n',''))
  a = list(map(int,args[tc*3+1].replace('\n','').split()))
  s = args[tc*3+2].replace('\n','')
  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:
import sys


MAX_BIT_LEN = 60

def main():
    file_contents = sys.stdin.read().split('\n')
    T = int(file_contents[0])
    file_contents_ix = 1
    for t in range(T):
        N = int(file_contents[file_contents_ix])
        A = list(map(int, file_contents[file_contents_ix+1].split()))
        S = file_contents[file_contents_ix+2].strip()
        file_contents_ix += 3
        print(solve(N, A, S))

def solve(N, A, S):
    masks_by_bit = [0] * MAX_BIT_LEN
    for i in range(len(A) - 1, -1, -1):
        player = S[i]
        mask = A[i]
        if player == '0':
            add_to_bit_mask(masks_by_bit, mask)
        if player == '1':
            if not check_if_spanned(masks_by_bit, mask):
                return '1'
    return 0

# Useful algo: https://math.stackexchange.com/questions/2150103/xor-number-combinations, similar to Gaussian elim
# Returns a linearly independent set.
# Inspired by the above
def add_to_bit_mask(masks_by_bit, mask):
    while masks_by_bit[mask.bit_length() - 1]:
        mask ^= masks_by_bit[mask.bit_length() - 1]
    if mask:
        masks_by_bit[mask.bit_length() - 1] = mask

def check_if_spanned(masks_by_bit, mask):
    while masks_by_bit[mask.bit_length() - 1]:
        mask ^= masks_by_bit[mask.bit_length() - 1]
    return not mask


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) 
    setp1xor = set(p1xor)
    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 setp1xor:
                   setp1xor.add(temp)

    # xorのリスト
    p0xor = copy.copy(p0) 
    setp0xor = set(p0xor) 
    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 setp0xor:
                    setp0xor.add(temp)

    
    flag = True
    for p in setp1xor:
        if p not in setp0xor:
            flag = False
            break
    if flag == True:
        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()
    key = int(s[-1])
    wset = {0}
    setlist = []#逆順になる
    manlist = []#逆順になる
    index = -1
    if(key == 1):
        print(1)
    else:
        for j in range(n):
            temp = int(s[-(j+1)])
            if(temp == key):
                tempset = set()
                for k in wset:
                    tempset.add(k ^ a[-(j+1)])
                wset = wset | tempset
            else:
                setlist.append(wset)
                manlist.append(key)
                index += 1
                if(key == 1 and index > 1):
                    if(setlist[index] - setlist[index-1] != set()):
                        print(1)
                        break
                key = temp
                wset = {0, a[-(j+1)]}
        setlist.append(wset)
        manlist.append(key)
        if(manlist[-1] == 1):
            if(setlist[-1] - setlist[-2] != set()):
                print(1)
            else:
                print(0)
        else:
            print(0)

Submission status: Time Limit Exceeded

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

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



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

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                task = task | set(q)
                task = standard_form(np.array(list(task), np.int64))
                task = set(task)
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                q = set(q) | task
                q = standard_form(np.array(list(q), np.int64))
                q = set(q)
                if task != task | q:
                    win = "1"
                    break

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

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

    print(win)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    t = int(input())
    n = []
    a = []
    s = []
    for loop in range(t):
        n.append(int(input()))
        a.append(list(map(int, input().split())))
        s.append(list(map(int, list(input()))))

    for loop in range(t):
        zero_hands = []
        one_hands = []
        for turn in range(n[loop]):
            if s[loop][turn]==0:
                zero_hands.append(a[loop][turn])
            else :
                one_hands.append(a[loop][turn])

        if s[loop][-1]==0:  #last player zero
            success_flag = False
            for _ in range(2**len(one_hands)):
                success_flag = False
                num = 0
                for _2 in range(len(one_hands)):
                    temp = (_ >> _2) & 1
                    if temp==1:
                        num = num ^ one_hands[_2]
                    else:
                        pass

                for _2 in range(2**len(zero_hands)):
                    num2 = 0
                    for _3 in range(len(zero_hands)):
                        temp = (_2 >> _3) & 1
                        if temp==1:
                            num2 = num2 ^ zero_hands[_3]
                    if num==num2:
                        success_flag = True
                        break

                if success_flag==False:
                    break

            if success_flag==True:
                print('0')
            else:
                print('1')
                
        else:   #last player one
            success_flag = False
            for _ in range(2**len(zero_hands)):
                success_flag = False
                num = 0
                for _2 in range(len(zero_hands)):
                    temp = (_ >> _2) & 1
                    if temp==1:
                        num = num ^ zero_hands[_2]
                    else:
                        pass

                for _2 in range(2**len(one_hands)):
                    num2 = 0
                    for _3 in range(len(one_hands)):
                        temp = (_2 >> _3) & 1
                        if temp==1:
                            num2 = num2 ^ one_hands[_3]
                    if num!=num2:
                        success_flag = True
                        break

                if success_flag==False:
                    break

            if success_flag==True:
                print('1')
            else:
                print('0')

Submission status: Time Limit Exceeded

Solution code:
import itertools

def hatt(my_list):
  count = 0
  for i in my_list:
    count = count ^ i
  return(count)

ans = []
T = int(input())
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  # x = 0
  
  list_0 = [A[i] for i in range(N) if S[i] == '0']
  list_1 = [A[i] for i in range(N) if S[i] == '1']

  result_0 = []
  for n in range(len(list_0) + 1):
    for comb in itertools.combinations(list_0, n):
      result_0.append(hatt(comb))
  nums_0 = set(result_0)

  result_1 = []
  for n in range(len(list_1) + 1):
    for comb in itertools.combinations(list_1, n):
      result_1.append(hatt(comb))
  nums_1 = set(result_1)
  
  ans.append(1 if sum([num not in nums_0 for num in nums_1]) else 0)

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