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:
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):
    S = S[::-1]
    A = A[::-1]
    if S[0] != '0':
        return '1'
    current_ix = 0
    end_ix = 1
    masks_by_bit = [0] * MAX_BIT_LEN
    for player, mask in zip(S, A):
        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:
#!python3

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

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

    s0 = "0"
    st = {0,}
    aa = [st]
    for ai, si in zip(a, s):
        if s0 == si:
            tmp = [x^ai for x in st]
            st.update(tmp)
        else:
            st = {0, ai,}
            aa.append(st)
            s0 = si

    a3 = set()
    for i in range(len(aa)-1, 0, -2):
        a0, a1 = aa[i], aa[i-1]
        a0 |= a3
        if a1 <= a0:
            a3 = a0 - a1
        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:
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:
      return 0
    elif x == 0 :
      return 0
    else:
      return 1
  ret = judge(k,si + 1,x,alist)
  ret1 = judge(k,si + 1,x^alist[si],alist)
  if ret != 0 or ret1 != 0:
    return 1
  return 0

for tc in range(t):
  n = int(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:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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

    return f(0, 0)

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

    if len(al[1]) == 0:
        return 0

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


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

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

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


def main():
    T = read_int()
    for _ in range(T):
        N = read_int()
        A = read_int_n()
        S = read_str()
        if N > 30:
            N = 30
            A = A[:-30]
            S = S[:-30]
        print(ref(N, A, S))


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

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


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


if __name__ == '__main__':
    main()

Submission status: 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 = np.array(L0) ^ A[i]
            L0.extend(list(tmp))
            L0 = set(L0)
            L0 = list(L0)
        if s == "1":
            tmp = np.array(L1) ^ A[i]
            L1.extend(list(tmp))
            L1 = set(L1)
            L1 = list(L1)

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

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

def xorseto(i,j):
    if j==len(o):
        so.add(i)
    else:
        xorseto(i^o[j],j+1)
        xorseto(i,j+1)
    
def xorsetp(i,j):
    if j==len(p):
        sp.add(i)
    else:
        xorsetp(i^p[j],j+1)
        xorsetp(i,j+1)
    
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()  
    xorseto(0,0)
    sp = set()
    xorsetp(0,0)
    
    if so - sp:
        print(1)
    else:
        print(0)

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 = set()
        A1 = set()
        for a, s in zip(A, S):
            if s == 1:
                A0.add(a)
            elif s == 0:
                A1.add(a)

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

        is_subset = True
        X = set([0])
        for a in A1:
            Z = set()
            if a not in X:
                for x in X:
                    Z.add(a ^ x)

            if not Z <= Y:
                is_subset = False
                break
            X |= Z

        ret.append(0 if is_subset 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
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(list(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(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"
                    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:
MAX_BIT_LEN = 60

def main():
    T = int(input())
    for t in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input().strip()
        print(solve(N, A, S))

def solve(N, A, S):
    S = S[::-1]
    A = A[::-1]
    if S[0] != '0':
        return '1'
    current_ix = 0
    end_ix = 1
    masks_by_bit = [0] * MAX_BIT_LEN
    for player, mask in zip(S, A):
        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:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


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


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


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


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


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


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

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


def mt(f):
    import time

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

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

    return wrap


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

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

    return f(0, 0)

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

    if len(al[1]) == 0:
        return 0

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


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

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

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


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


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

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main(L1, k):
    if L1 == 0:
        return 1
    if k == -1:
        if L1 == 0:
            return 1
        else:
            return 0
    if (L1 >> k) & 1:
        for f0 in F0[k]:
            if main(L1 ^ f0, k - 1):
                return 1
        return 0
    else:
        return main(L1, k - 1)


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

    L0 = []
    L1 = []
    for i in range(N):
        if S[i] == "1":
            L1.append(A[i])
        else:
            L0.append(A[i])

    L00 = L0[:]
    for i in range(len(L0)):
        for j in range(len(L0)):
            L00.append(L0[i] ^ L0[j])

    L0 = list(set(L00))

    F0 = [[] for i in range(62)]
    for l0 in L0:
        k = l0
        t = 0
        for i in range(62):
            if l0 & 1:
                t = i
            l0 >>= 1
        F0[t].append(k)

    f = 1
    for l1 in L1:
        if main(l1, 61):
            continue
        else:
            f = 0
            break
    if f:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    for t in range(T):
        n = int(input())
        A = list(map(int, input().split()))
        s = input()
        if s[-1] == "1":
            print(1)
            break
        p1 = deque([0])
        p2 = deque([0])
        c1 = [A[i] for i in range(n) if s[i] == "0"]
        c2 = [A[i] for i in range(n) if s[i] == "1"]

        def dfs1(x, n):
            if n == len(c1):
                p1.append(x)
                return
            dfs1(x, n + 1)
            dfs1(x ^ c1[n], n + 1)

        def dfs2(x, n):
            if n == len(c2):
                p2.append(x)
                return
            dfs2(x, n + 1)
            dfs2(x ^ c2[n], n + 1)

        dfs1(0, 0)
        dfs2(0, 0)
        # print(set(p1), set(p2))
        if len(set(p1) ^ set(p2)) == 0:
            print(0)
        else:
            print(1)

resolve()

Submission status: Time Limit Exceeded

Solution code:
def kosu(kitei, aaa):
    ret = 0
    n=len(kitei)
    for i in range(n):
        if kitei[i]:
            ret += 1
            x = 0
            while (2**(x+1)) <= kitei[i]:
                x += 1
            for y in range(i+1, n, 1):
                if kitei[y] & (2 ** x):
                    kitei[y] ^= kitei[i]
    
    ret2=0
    kitei.append(aaa)
    n+=1
    for i in range(n):
        if kitei[i]:
            ret2 += 1
            x = 0
            while (2**(x+1)) <= kitei[i]:
                x += 1
            for y in range(i+1, n, 1):
                if kitei[y] & (2 ** x):
                    kitei[y] ^= kitei[i]
    
    if ret==ret2:
        return 1
    else:
        return 0


def solve(n, alist, s):
    kitei=[0]
    answer=0
    for i in range(n):
        teban=s[n-i-1]
        now=alist[n-i-1]
        if teban=='0':
            if kosu(kitei, now)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer


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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main(L1, k):
    if k == -1:
        if L1 == 0:
            return 1
        else:
            return 0
    if (L1 >> k) & 1:
        for f0 in F0[k]:
            if main(L1 ^ f0, k - 1):
                return 1
        return 0
    else:
        return main(L1, k - 1)


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

    L0 = []
    L1 = []
    for i in range(N):
        if S[i] == "1":
            L1.append(A[i])
        else:
            L0.append(A[i])

    L00 = L0[:]
    for i in range(len(L0)):
        for j in range(len(L0)):
            L00.append(L0[i] ^ L0[j])

    L0 = list(set(L00))

    F0 = [[] for i in range(62)]
    for l0 in L0:
        k = l0
        t = 0
        for i in range(62):
            if l0 & 1:
                t = i
            l0 >>= 1
        F0[t].append(k)

    f = 1
    for l1 in L1:
        if main(l1, 61):
            continue
        else:
            f = 0
            break
    if f:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import os
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from io import BytesIO, IOBase
from typing import Dict, List, Optional, Set, Tuple


def get_bits(n: int) -> Set[int]:
    result = set()
    i = 0
    while n:
        n, r = divmod(n, 2)
        if r:
            result.add(i)
        i += 1
    return result


def solve(values: List[int], _nb: int, s: str) -> bool:
    bits_0 = set()
    bits_1 = set()
    for p, n in zip(s, values):
        new_bits = get_bits(n)
        if p == "0":
            bits_0.update(new_bits)
        else:
            bits_1.update(new_bits)
    if not bits_0.issuperset(bits_1):
        return False
    nbs_0 = set()
    nbs_1 = set()
    for p, n in zip(s, values):
        if p == "0":
            if not nbs_1:
                continue
            next_0 = set(k ^ n for k in nbs_0)
            nbs_0.add(n)
            nbs_0.update(next_0)
            nbs_1.difference_update(nbs_0)
        else:
            next_1 = set(k ^ n for k in nbs_1)
            nbs_1.add(n)
            nbs_1.update(next_1)
            nbs_0 = set()
    # LOG.debug((bits_0, bits_1))
    return not bool(nbs_1)


def do_job(stdin, stdout):
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    T = int(stdin.readline().strip())
    for _ in range(T):
        N = int(stdin.readline().strip())
        values = list(map(int, stdin.readline().split()))
        S = stdin.readline().strip()
        result = solve(values, N, S)
        print(0 if result else 1, file=stdout)


def print_output(testcase: int, result, stdout) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result), file=stdout)
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result), file=stdout)


BUFSIZE = 8192


class FastIO(IOBase):
    # pylint: disable=super-init-not-called, expression-not-assigned
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    # pylint: disable=super-init-not-called
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(IOWrapper(sys.stderr))
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    stdin = IOWrapper(sys.stdin)
    stdout = IOWrapper(sys.stdout)
    do_job(stdin, stdout)
    stdout.flush()
    for h in LOG.handlers:
        h.flush()
    return 0


if __name__ == "__main__":
    sys.exit(main())

Submission status: Time Limit Exceeded

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

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

t = int(input())
x = 0

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

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    key = int(s[-1])
    wset = {0}
    setlist = []#逆順になる
    manlist = []#逆順になる
    if(key == 1):
        print(1)
    else:
        for j in range(n):
            temp = int(s[-(j+1)])
            if(temp == key):
                tempset = set()
                for k in wset:
                    tempset.add(k ^ a[-(j+1)])
                wset = wset | tempset
            else:
                setlist.append(wset)
                manlist.append(key)
                key = temp
                wset = {0, a[-(j+1)]}
        setlist.append(wset)
        manlist.append(key)
        if(manlist[0] == 1): print(1)
        else:
            for i in range(len(manlist)):
                if(manlist[i] == 0):
                    if(i+1 <len(manlist)):
                        if(setlist[i+1] - setlist[i] != set()):
                            print(1)
                            break
                    else:
                        print(0)
                elif(i+1 == len(manlist)):
                    print(0)

Submission status: Time Limit Exceeded

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

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

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

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

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

    setp0 = set(p0xor)

    if (setp1 - setp0) == set():
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

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

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

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

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

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

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