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())
#h1,m1,h2,m2,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

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

        k=0

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

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":
            for l0 in L0:
                if l0 ^ A[i] not in L0:
                    L0.append(l0 ^ A[i])
        if s == "1":
            for l1 in L1:
                if l1 ^ A[i] not in L1:
                    L1.append(l1 ^ A[i])
    if set(L0) <= set(L1):
        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 = input().split()
		# 人0 or 1
		S = list(input())
		# 最後がプレーヤー１の場合
		if S[-1] == '1':
			print('1')
		else:
			# プレーヤー毎のxor結果のパターンを考える
			pattern1 = {0}
			pattern2 = {0}
			for i in range(N):
				a = int(A[i])
				if S[i]=='1':
					pattern1 = pattern1 | {x^a for x in pattern1}
				else:
					pattern2 = pattern2 | {x^a for x in pattern2}
			if len(pattern1 - pattern2) > 0:
				print('1')
			else:
				print('0')

resolve()

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=[]
        p0=set()
        p1=set()
        for i in range(N):
            if S[i]=='0':
                S0.append(A[i])
            else:
                p1.add(A[i])

        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:
from itertools import product
from typing import List


class Phase:
    def __init__(self, player):
        self.player = player
        self.commmands = []

    def __repr__(self):
        return f"{self.player} with {self.commmands}"


def parse_phases(S, A) -> List[Phase]:
    phases = []
    for i, s in enumerate(S):
        if len(phases) == 0 or phases[-1].player != int(s):
            phases.append(Phase(int(s)))
        phases[-1].commmands.append(A[i])
    return phases


def calc_patterns(x, commmands):
    r = []
    for p in product(*[(False, True) for _ in commmands]):
        y = x
        for i, b in enumerate(p):
            if b:
                y = y ^commmands[i]
        r.append(y)
    return r


def calc_game(S, A):
    x = 0
    phases = parse_phases(S, A)
    if phases[-1].player == 1:
        return "1"
    for p in phases:
        patterns = calc_patterns(x, p.commmands)
        x = min(patterns) if p.player == 0 else max(patterns)
    return "1" if x > 0 else "0"


if __name__ == "__main__":
    # 整数1個だけ
    T = int(input().strip())
    for _ in range(T):
        N = int(input().strip())
        A = [int(x) for x in input().strip().split(" ")]
        S = input().strip()
        # import pdb; pdb.set_trace()
        print(calc_game(S, A))

Submission status: Time Limit Exceeded

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

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

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

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

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

t = int(input())

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

    d = {'0': set(), '1': set()}
    for i in range(n):
        d[s[i]].add(a[i])

    arr = list(d['0'])    
    for bit_array in range(1 << len(arr)):
        bit = bit_array
        s = 0
        while bit:
            idx = int(math.log2(bit & ~(bit - 1)))
            s ^= arr[idx]
            bit &= bit - 1
        if s in d['1']:
            d['1'].remove(s)
        if not d['1']:
            break

    if d['1']:
        print('1')
    else:
        print('0')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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

    # @lru_cache(None)
    def gen_patterns(self, cur: int, candidates: list):
        if not candidates:
            return
        else:
            candidate = candidates[0]
            self.pat.add(cur ^ candidate)
            self.pat.add(cur)
            self.gen_patterns(cur ^ candidate, candidates[1:])
            self.gen_patterns(cur, candidates[1:])


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

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

        if not p1.pat.issubset(p0.pat):
            ans[j] = 1
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def select(x2, A, S, cur_i):
  num = len(bin(x2)) -2
  cand = []
  for i in range(num):
    if x2 >> i & 1:
      cand.append(i)
  cand_a = []
  for i, s in enumerate(S):
    if i > cur_i and s == 0:
      a = A[i]
      num_a = len(bin(a)) -2
      for j in range(num_a):
        if a >> j & 1:
          cand_a.append(j)
  cand_a = set(cand_a)
  uni_cnt = 0
  for c in cand:
    if c not in cand_a:
      return True
  return False         
      
def solve(N, A, S):
  x = 0
  x2 = 0
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    if S[i] == 1:
      #if popcount(x2) >= popcount(x):
      #  x = x2
      #else:
      if select(x2, A, S, i):
        x = x2
        print(1)
        return
    else:
      if popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    print(0)
  else:
    print(1)

T = int(input())
for _ in range(T):
  N = int(input())
  A = [int(i) for i in input().split()]
  S = [int(i) for i in input()]
  solve(N, A, S)

Submission status: Time Limit Exceeded

Solution code:
import math

t = int(input())

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

    d = {'0': set(), '1': set()}
    for i in range(n):
        d[s[i]].add(a[i])

    arr1 = list(d['1'])
    res = set()
    for bit_array in range(1 << len(arr1)):
        bit = bit_array
        s = 0
        while bit:
            idx = int(math.log2(bit & ~(bit - 1)))
            s ^= arr1[idx]
            bit &= bit - 1
        res.add(s)
    arr2 = list(d['0'])    
    for bit_array in range(1 << len(arr2)):
        bit = bit_array
        s = 0
        while bit:
            idx = int(math.log2(bit & ~(bit - 1)))
            s ^= arr2[idx]
            bit &= bit - 1
        if s in res:
            res.remove(s)
        if not res:
            break

    if res:
        print('1')
    else:
        print('0')

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def select(x2, A, S, cur_i):
  num = len(bin(x2)) -2
  cand = []
  for i in range(num):
    if x2 >> i & 1:
      cand.append(i)
  cand_a = []
  for i, s in enumerate(S):
    if i > cur_i and s == 0:
      a = A[i]
      num_a = len(bin(a)) -2
      for j in range(num_a):
        if a >> j & 1:
          cand_a.append(j)
  cand_a = set(cand_a)
  uni_cnt = 0
  for c in cand:
    if c not in cand_a:
      return True
  return False         
      
def solve(N, A, S):
  x = 0
  x2 = 0
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    if S[i] == 1:
      #if popcount(x2) >= popcount(x):
      #  x = x2
      #else:
      if select(x2, A, S, i):
        x = x2
    else:
      if popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    print(0)
  else:
    print(1)

T = int(input())
for _ in range(T):
  N = int(input())
  A = [int(i) for i in input().split()]
  S = [int(i) for i in input()]
  solve(N, A, S)

Submission status: Time Limit Exceeded

Solution code:
# copied from stackoverflow

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


def eliminate(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[:]
            # print(values)
            eliminated_values = eliminate(values)
            # print(eliminated_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())
import time
st=time.time()
for _ in range(t):
    ans=-1
    n=int(input())
    a=[int(j)for j in input().split()]
    s=input()
    if s[-1]=="1":
        ans=1
        print(ans)
    if ans==-1:
        lz=set()
        ll=set()
        lo=set()
        for i,j in zip(a,s):
            if j=="1":
                lo.add(i)
                lz=set()
            else:
                if i in lo:
                    lo.remove(i)
                lz.add(i)
        cz=[0]*60
        for i in lz:
            for j in range(60):
                cz[j]+=i>>j&1
        co=[0]*60
        for i in lo:
            for j in range(60):
                co[j]+=i>>j&1
        for i,j in zip(cz,co):
            if i<j:
                ans=1
                print(1)
                break
        if ans==-1:
            l=set()
            m=len(lz)
            lz=list(lz)
            for i in range(1<<m):
                tmp=0
                for j in range(m):
                    if i>>j&1:
                        tmp^=lz[j]
                l.add(tmp)
            m=len(lo)
            lo=list(lo)
            for i in range(1<<m):
                if time.time()-st>1500:
                    print(1)
                tmp=0
                for j in range(m):
                    if i>>j&1:
                        tmp^=lo[j]
                if tmp not in l:
                    ans=1
                    print(1)
            if ans==-1:
                print(0)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def select(x2, A, S):
  num = len(bin(x2)) -2
  cand = []
  for i in range(num):
    if x2 >> i & 1:
      cand.append(i)
  cand_a = []
  for i, s in enumerate(S):
    if s == 0:
      a = A[i]
      num_a = len(bin(a)) -2
      for j in range(num_a):
        if a >> j & 1:
          cand_a.append(j)
  cand_a = set(cand_a)
  uni_cnt = 0
  for c in cand:
    if c not in cand_a:
      return True
  return False         
      
def solve(N, A, S):
  x = 0
  x2 = 0
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    if S[i] == 1:
      #if popcount(x2) >= popcount(x):
      #  x = x2
      #else:
      if select(x2, A, S):
        x = x2
    else:
      if popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    print(0)
  else:
    print(1)

T = int(input())
for _ in range(T):
  N = int(input())
  A = [int(i) for i in input().split()]
  S = [int(i) for i in input()]
  solve(N, A, S)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 組み合わせ・N^2
# x=0となるのは x=Aiのとき
# 1は0の手駒で作れない数字を作りたい
# 0は1の手駒で作れてしまう数字を作りたい
# 各人0と人1のターン毎に最適な行動をとろうとするものと仮定
import re
import itertools

t = int(input())
for idx in range(0, t):
    n = int(input())
    arr = list(map(int, input().split(' ')))
    s = input()

    # s を 0...01...1 または 1...10...0 に分割する
    count_zero = 0
    count_one = 0
    for si in s:
        if si == '0':
            count_zero = count_zero + 1
        elif si == '1':
            count_one = count_one + 1

    if s.endswith('0'):
        ones = arr[0:count_one]
        zeros = arr[count_one:]
        
    elif s.endswith('1'):
        zeros = arr[0:count_zero] 
        ones = arr[count_zero:]

    zero_pairs = []
    for n in range(1, len(zeros)+1):
        for conb in itertools.combinations(zeros, n):
            val = 0
            for num in conb:
                val = val^num
            zero_pairs.append(val)
    
    one_pairs = []
    for n in range(1, len(ones)+1):
        for conb in itertools.combinations(ones, n):
            val = 0
            for num in conb:
                val = val^num
            one_pairs.append(val)
    
    if (s.endswith('0')):
        if (set(zero_pairs) & set(one_pairs)):
            print(0)
        else:
            print(1)
    else:
        if (set(zero_pairs) & set(one_pairs)):
            print(1)
        else:
            print(0)

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 = list(map(int, input().split()))
		# 人0 or 1
		S = input()
		# 最後がプレーヤー１の場合
		if S[-1] == '1':
			print('1')
		else:
			# プレーヤー毎のxor結果のパターンを考える
			pattern1 = [0]
			pattern2 = [0]
			for i in range(N):
				if S[i]=='1':
					pattern1 += [x^A[i] for x in pattern1]
				else:
					pattern2 += [x^A[i] 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:
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    p1 = []
    p0 = []
    for i, ss in enumerate(s):
        p1.append(a[i]) if ss == "1" else p0.append(a[i])
    p11 = set()
    p00 = set()
    
    def make_set(data, ans):
        res = 0
        for i in range(1 << len(data)):
            for j in range(len(data)):
                if (i >> j) & 1 == 1:
                    res ^= data[j]
                ans.add(res)

    make_set(p1, p11)
    make_set(p0, p00)
    print(0 if p00 == p11 else 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
	return sys.stdin.readline()[:-1]

def rank(a):
	n, m = len(a), len(a[0])
	#a = np.array([list(map(int, input().split())) for _ in [0]*n])
	if n > m:
		a = a.T
		n, m = m, n
	r = 0
	for i in range(n):
		if a[i][i] != 1:
			for j in range(i+1, m):
				if a[i][j] == 1:
					a[:, [i, j]] = a[:, [j, i]]
					break
			else:
				for j in range(i+1, n):
					if a[j][i] == 1:
						a[[i, j]] = a[[j, i]]
					break
				else:
					break
		if a[i][i] == 0:
			continue

		r += 1
		for j in range(i+1, m):
			a[:, j] ^= a[i][j] * a[:, i]
		for j in range(i+1, n):
			a[j] ^= a[j][i] * a[i]
	
	return r
	#print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	if s[-1] == "1":
		print(1)
		continue
	else:
		i = 0
		z, zo = [], []
		for i in range(n):
			if s[i] == "1":
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				
			else:
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				z.append([(a[i] >> k) & 1 for k in range(60)])
				
		#print(z, zo)
		if rank(np.array(z)) != rank(np.array(zo)):
			print(1)
		else:
			print(0)

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):
    l = len(aa)
    sets = {0}
    for aaa in aa:
        buf = sets.copy()
        for b in buf:
            sets.add(b ^ aaa)
    return sets

for i in range(t):
    if s[i][-1] == '1':
        print(1)
    else:
        l = s[i].rfind('1')+1
        aa = set(a[i][:l])
        sets = ret_set(aa)
        aa = set(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 popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def select(x2, A, S):
  num = len(bin(x2)) -2
  cand = []
  for i in range(num):
    if x2 >> i & 1:
      cand.append(i)
  cand_a = []
  for i, s in enumerate(S):
    if s == 0:
      a = A[i]
      num_a = len(bin(a)) -2
      for j in range(num_a):
        if a >> j & 1:
          cand_a.append(j)
  cand_a = set(cand_a)
  uni_cnt = 0
  for c in cand:
    if c not in cand_a:
      return True
  return False         
      
def solve(N, A, S):
  x = 0
  x2 = 0
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    if S[i] == 1:
      if popcount(x2) > popcount(x):
        x = x2
      else:
        if select(x2, A, S):
          x = x2
    else:
      if popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    print(0)
  else:
    print(1)

T = int(input())
for _ in range(T):
  N = int(input())
  A = [int(i) for i in input().split()]
  S = [int(i) for i in input()]
  solve(N, A, S)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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(c)
        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:
import numpy as np
import sys
def input():
	return sys.stdin.readline()[:-1]

def rank(a):
	n, m = len(a), len(a[0])
	#a = np.array([list(map(int, input().split())) for _ in [0]*n])
	if n > m:
		a = a.T
		n, m = m, n
	r = 0
	for i in range(n):
		if a[i][i] != 1:
			for j in range(i+1, m):
				if a[i][j] == 1:
					a[:, [i, j]] = a[:, [j, i]]
					break
			else:
				for j in range(i+1, n):
					if a[j][i] == 1:
						a[[i, j]] = a[[j, i]]
					break
				else:
					break
		if a[i][i] == 0:
			continue

		r += 1
		for j in range(i+1, m):
			a[:, j] += a[i][j] * a[:, i]
			a[:, j] %= 2
		for j in range(i+1, n):
			a[j] += a[j][i] * a[i]
			a[j] %= 2
	
	return r
	#print((pow(2, n+m-1, MOD) - pow(2, n+m-r-1, MOD)) % MOD)

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	if s[-1] == "1":
		print(1)
		continue
	else:
		i = 0
		z, zo = [], []
		for i in range(n):
			if s[i] == "1":
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				
			else:
				zo.append([(a[i] >> k) & 1 for k in range(60)])
				z.append([(a[i] >> k) & 1 for k in range(60)])
				
		#print(z, zo)
		if rank(np.array(z)) != rank(np.array(zo)):
			print(1)
		else:
			print(0)

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 += [x^a for x in pattern1]
				else:
					pattern2 += [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()