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: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = set([0])
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if S[-i] == '1':
                print('1')
                break
            else:
                base.add(temp)
    else:
        print('0')

Submission status: Wrong Answer

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=10**9+7):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] = (M[i][k]+M[j][k]) % mod
                        break
                else:
                    for j in range(i+1, m):
                        if M[i][j] != 0:
                            for k in range(i, n):
                                M[k][i] = (M[k][i]+M[k][j]) % mod
                            break
                    else:
                        rank -= 1
            pinv = pow(M[i][i], mod-2, mod)
            for j in range(m):
                M[i][j] = M[i][j]*pinv % mod
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] = (M[j][k]-M3*M2[k]) % mod
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    if newr != r+1:
                        print(1/0)
                    r += 1
                    m += b
            else:
                if newr > r:
                    if newr != r+1:
                        print(1/0)
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Wrong Answer

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=10**9+7):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] = (M[i][k]+M[j][k]) % mod
                        break
                else:
                    for j in range(i+1, m):
                        if M[i][j] != 0:
                            for k in range(i, n):
                                M[k][i] = (M[k][i]+M[k][j]) % mod
                            break
                    else:
                        rank -= 1
            pinv = pow(M[i][i], mod-2, mod)
            for j in range(m):
                M[i][j] = M[i][j]*pinv % mod
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] = (M[j][k]-M3*M2[k]) % mod
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = set([0])
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if temp not in base:
                if S[-i] == '1':
                    print('1')
                    break
                else:
                    base.add(temp)
    else:
        print('0')

Submission status: Wrong Answer

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=10**9+7):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] = (M[i][k]+M[j][k]) % mod
                        break
                else:
                    rank -= 1
            pinv = pow(M[i][i], mod-2, mod)
            for j in range(m):
                M[i][j] = M[i][j]*pinv % mod
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] = (M[j][k]-M3*M2[k]) % mod
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Wrong Answer

Solution code:
T = int(input())

for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    x = 0
    for i in range(n):
        if s[i] == '0':
            x = x ^ a[i]
        else:
            pass
    if x == '0':
        print(x)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
T = int(input())

for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    x = 0
    for i in range(n):
        if s[i] == '0':
            x = x | a[i]
        else:
            pass
    if x == '0':
        print(x)
    else:
        print(1)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    dp={0}
    for i in range(n-1,-1,-1):
        now=a[i]
        if s[i]=="0":
            if now in dp:
                continue
            for j in dp:
                if now^j<now:
                    now=now^j
                    if now in dp:
                        break
            else:
                dp.add(now)
        else:
            for j in dp:
                if (now^j in dp)or(now in dp):
                    break
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    dp={0}
    for i in range(n-1,-1,-1):
        now=a[i]
        if s[i]=="0":
            if now in dp:
                continue
            for j in dp:
                if now^j<now:
                    now=now^j
                    if now in dp:
                        break
            else:
                dp.add(now)
        else:
            for j in dp:
                if now^j in dp:
                    break
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    dp={0}
    for i in range(n-1,-1,-1):
        #print(dp)
        now=a[i]
        if s[i]=="0":
            for j in dp:
                if now^j<now:
                    now=now^j
            dp.add(now)
        else:
            for j in dp:
                if now^j in dp:
                    break
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
I=input
n=int
for i in range(int(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t.append(i*(j^1));x|=i&j
  print(x)

Submission status: Wrong Answer

Solution code:
I=input
n=int
for i in range(int(input())):
  I();t=[];x=0
  for i,j in zip(map(n,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    j=n(j);t.append(i*j);x|=i&j
  print(x)

Submission status: Wrong Answer

Solution code:
I=input
for i in range(int(I())):
  I()
  t=[]
  x=0
  for i,j in zip(map(int,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    t.append(i*(j=="0"))
    x|=i&(j=="1")
  print(x)

Submission status: Wrong Answer

Solution code:
I=input
for i in range(int(I())):
  I()
  t=[]
  x=0
  for i,j in zip(map(int,I().split()[::-1]),I()[::-1]):
    for k in t:i^=k*(i^k<i)
    t.append(i*(j=="0"))
    x=i&(j=="1")
  print(x)

Submission status: Wrong Answer

Solution code:
#Testing other people code


T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    X = [0 for i in range(71)]
    Y = 0
    for i in range(N - 1, -1, -1):
        a = A[i]
    if S[i] == '0':
        for i in range(70, -1, -1):
            if (a>>i) % 2 == 1:
                a = a ^ X[i]
            if a:
                X[len(bin(a)) - 3] = a
    else:
        for i in range(70, -1, -1):
            if (a>>i) % 2 == 1:
                a = a ^ X[i]
            if a != 0:
                Y = 1
                break
    print(Y)

Submission status: Wrong Answer

Solution code:
T=int(input())
for t in range(T):
    N=int(input())
    A=list(map(int,input().split()))[::-1]
    S=input()
    S=[1 if c=='1' else 0 for c in S][::-1]
    l=[]
    r=0
    for i,a in enumerate(A):
        if S[i]:
            for e in l:
                if a&e:
                    a^=e
            if a:
                r=1
        else:
            for e in l:
                if a>e^a:
                    a=e^a
            if a:
                for i in range(len(l)):
                    l[i]-=l[i]&a
                l.append(a)
    print(r)

Submission status: Wrong Answer

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        L = max(A).bit_length()
        s = [0]*L

        def check(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            return(x == 0)

        def update(x):
            for i in range(L-1, -1, -1):
                if (x >> i) % 2:
                    x ^= s[i]
            s[x.bit_length() - 1] = x

        res = 0
        for i in range(N-1, -1, -1):
            k = int(S[i])
            # print(A[i], dp[i+1], k)
            if k:
                if check(A[i]):
                    continue
                else:
                    res = 1
                    break
            else:
                update(A[i])
        # print(dp)
        print(res)


main()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def kitei(SET,b):
  for k in SET:
    if k^b < b:
      b = k^b
  return {b}

def can_made_by(SET,b):
  if SET == set():
    return False
  for k in SET:
    if k^b < b:
      b = k^b
  if b:
    return False
  else:
    return True


def solve():
  N = I()
  A = IL()
  S_ = S()
  
  dp = [None for i in range(N+1)]
  dp[N] = {0}
  for i in range(N)[::-1]:
    if S_[i] == "0":
      dp[i] = dp[i+1] | kitei(dp[i+1],A[i])
    else:
      if can_made_by(dp[i+1],A[i]):
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  if can_made_by(dp[0],0):
    print(0)
  else:
    print(1)

T = I()
for _ in range(T):
  solve()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def kitei(SET,b):
  for k in SET:
    if k^b < b:
      b = k^b
  return {b}

def can_made_by(SET,b):
  for k in SET:
    if k^b < b:
      b = k^b
  if b:
    return False
  else:
    return True


def solve():
  N = I()
  A = IL()
  S_ = S()
  
  dp = [None for i in range(N+1)]
  dp[N] = {0}
  for i in range(N)[::-1]:
    if S_[i] == "0":
      dp[i] = dp[i+1] | kitei(dp[i+1],A[i])
    else:
      if can_made_by(dp[i+1],A[i]):
        dp[i] = dp[i+1]
      else:
        dp[i] = set()
  if dp[0] == set():
    print(1)
  else:
    print(0)

T = I()
for _ in range(T):
  solve()

Submission status: Wrong Answer

Solution code:
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return sorted(arr[:rank])

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = []

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a & b0:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(B0+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return sorted(arr[:rank], reverse=True)

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = []

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a & b0:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(B0+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
T = int(input())

def check_base(bases, A):
	for n, b in bases:
		if A & (1 << n) != 0:
			A ^= b
	if A == 0:
		return None
	n = 0
	d = 1
	while True:
		if A & d != 0:
			return n, d
		n += 1
		d <<= 1

def append_base(bases, A):
	pair = check_base(bases, A)
	if pair != None:
		bases.append(pair)

def check(N, A_list, S):
	bases = []
	for i in range(N - 1, -1, -1):
		A = A_list[i]
		if S[i] == "0":
			append_base(bases, A)
		else:
			if check_base(bases, A):
				return False
	return True

for i in range(T):
	N = int(input())
	A_list = list(map(int, input().split()))
	S = input().strip()
	
	if check(N, A_list, S):
		print("0")
	else:
		print("1")

Submission status: Wrong Answer

Solution code:
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return set(arr)

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = set()

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a & b0 == b0:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(list(B0)+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = int(input())
n = []
a = []
s = []
for i in range(t):
    nn = int(input())
    n.append(nn)
    aa = list(map(int,input().split()))
    a.append(aa)
    ss = input()
    s.append(ss)
for i in range(t):
    x = 0
    for j in range(n[i]):
        if s[i][j] == "0":
            if j < n[i]-1:
                if x ^ a[i][j] ^ a[i][j+1] == 0:# and s[i][j+1] == "0":
                    x = x ^ a[i][j]
                elif x ^ a[i][j] == 0 or x != 0:
                    x = x ^ a[i][j]
            elif x ^ a[i][j] == 0:
                x = x ^ a[i][j]
        else:
            if j < n[i]-1:
                if x ^ a[i][j] ^ a[i][j+1] == 1:# and s[i][j+1] == "1":
                    x = x ^ a[i][j]
                elif x ^ a[i][j] != 0 or x == 0:
                    x = x ^ a[i][j]
            elif x ^ a[i][j] != 0:
                x = x ^ a[i][j]
    if x != 0:
        print("1")
    else:
        print("0")

Submission status: Wrong Answer

Solution code:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	basis = []
	ans = 0
	for i in range(n-1, -1, -1):
		for b in basis:
			a[i] = min(a[i], a[i]^b)
			if a[i]:
				if s[i] == "0":
					basis.append(a[i])
				else:
					ans = 1
					break
	print(ans)

Submission status: Wrong Answer

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])
        print(dp[i+1])
    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: Wrong Answer

Solution code:
def solve(N, A, S):
    dp = [[]]*(N + 1)
    dp[0].append(0)
    print(dp[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])
        print(dp[i+1])
    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: Wrong Answer

Solution code:
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue
 
        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]
 
        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


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

    hand = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            # 手持ちでvalを作れるか確認する
            hand.sort(reverse=True)
            for num in hand:
                if val & num == num:
                    val -= num
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            hand.append(val)
            # 手持ちは基底で管理するので掃き出し法を行う
            hand = xor_gauss_jordan(hand)


    if flag:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])
 
    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break
 
        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue
 
        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]
 
        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1
 
    return A


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

    memo_0 = [0]
    flag = False

    for i in range(n)[::-1]:
        val = a[i]
        if s[i] == "1":
            # 手持ちでvalを作れるか確認する。
            for min_ in memo_0:
                if val & min_ == min_:
                    val -= min_
            if val != 0:
                flag = True
        else:
            # valを手持ちに加える
            memo_0.append(val)
            memo_0 = xor_gauss_jordan(memo_0)
            memo_0.sort(reverse=True)

    if flag:
        print(1)
    else:
        print(0)