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())
cmpx = []
for h in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    x = []
    y = []
    m = len(str(bin(max(a))))
    for j in range(n):
        if(s[j] == '0'):
            x.append(a[j])
        else:
            y.append(a[j])
    t1 = [0]*m
    l1 = [0]*m
    for i in range(len(x)):
        a1 = str(bin(x[i])[2:])
        for j in range(1,len(a1)+1):
            if(a1[-j] == '1'):
                t1[j-1] ^= x[i]
                if(t1[j-1]&t1[j-1]-1 == 0):
                    l1[len(bin(t1[j-1]))-3] = 1
    q1 = 0
    z1 = []
    for i in range(len(l1)):
        if(l1[i] == 0):
            q1 += 2**i
    for i in range(len(t1)):
        c = t1[i]&q1
        if(c&c-1):
            z1.append(c)
            
    t2 = [0]*m
    l2 = [0]*m
    for i in range(len(y)):
        a2 = str(bin(y[i])[2:])
        for j in range(1,len(a2)+1):
            if(a2[-j] == '1'):
                t2[j-1] ^= y[i]
                if(t2[j-1]&t2[j-1]-1 == 0):
                    l2[len(bin(t2[j-1]))-3] = 1
    q2 = 0
    z2 = []
    for i in range(len(l2)):
        if(l2[i] == 0):
            q2 += 2**i
    for i in range(len(t2)):
        c = t2[i]&q2
        if(c&c-1):
            z2.append(c)
    cmp = 0
    if(q1 <= q2):
        for j in range(m):
            if(l1[j] > l2[j]):
                cmp = 1
                break
    else:
        cmp = 1
    print(cmp)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from sys import stdin
import numpy as np
import math
import pprint
T = int(stdin.readline().rstrip())

for i in range(T):
    # print("T=",i)
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    S = stdin.readline().rstrip()
    n = len(S)
    maxa = max(A)
    keta = int (math.log2(maxa) + 1)
    if S[-1] == "1":
        print(1)
    else:
        a =[]
        k = 1
        while S[-k] == "0" :
            a2 = bin(A[-k])[2:]
            a2 = a2.zfill(keta)
           
            a2 = list(a2)
            a2 = list(map(int,a2))
            # print(a2)
            a.append(a2)
            k += 1
            if k > n:
                break
        a = np.matrix(a)
        rank = np.linalg.matrix_rank(a)
        if rank == keta:
            print(0)
        else:
            rank2 = 0
            a =[]
            if k <= n:
                while S[-k] == "1" :
                    a2 = bin(A[-k])[2:]
                    a2 = a2.zfill(keta)
                   
                    a2 = list(a2)
                    a2 = list(map(int,a2))
                    # print(a2)
                    a.append(a2)
                    k += 1
                    if k > n:
                        break
                a = np.matrix(a)
                rank2 = np.linalg.matrix_rank(a)
            if rank > rank2 :
                print(0)
            else:
                print(1)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    index = 0
    for i in reversed(range(61)):
        if k & (1 << i) == 0: continue
        flag = 0
        for j in range(index, len(Nums)):
            if Nums[j] & (1 << i) == (1 << i):
                Nums[index], Nums[j] = Nums[j], Nums[index]
                break
        else: return False
        for j in range(index + 1, len(Nums)):
            Nums[j] ^= Nums[index]
    return True


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
K=60

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

    if S=="1"*N:
        print(1)
        continue
    
    M=[]
    C=[]
    for i in range(N):
        if S[i]=="0":
            M.append(A[i])
        else:
            C.append(A[i])

    L=len(M)
    E=M+C


#E[j]>>i:i行j列

    J=0
    for k in range(L):
        i=J
        if (E[k]>>i)%2==0:
                flag=1
                for I in range(i+1,K):
                    if i!=I and (E[k]>>I)%2==1 and flag==1:
                        flag=0
                        for j in range(N):
                            p=(E[j]>>i)%2
                            q=(E[j]>>I)%2

                            if p!=q:
                                E[j]=E[j]^(1<<i)^(1<<I)
                        

        if (E[k]>>i)%2:
            J+=1
            F=[]
            for j in range(N):
                F.append((E[j]>>i)%2)
                
            for I in range(min(N,K)):
                if (i!=I) and ((E[k]>>I)%2):
                    for j in range(N):
                        E[j]^=(F[j]<<I)
        
    H=0
    for i in range(K):
        f=0
        for j in range(L):
            f=max(f,(E[j]>>i)%2)

        if f==0:
            for j in range(L,N):
                if (E[j]>>i)%2:
                    H=1

    print(H)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    index = 0
    for i in reversed(range(60)):
        if k & (1 << i) == 0: continue
        flag = 0
        for j in range(index, len(Nums)):
            if Nums[j] & (1 << i) == (1 << i):
                Nums[index], Nums[j] = Nums[j], Nums[index]
                break
        else: return False
        for j in range(index + 1, len(Nums)):
            Nums[j] ^= Nums[index]
    return True


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = [0]
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
for t in range(int(input())):
    n = int(input())
    *a, = map(int,input().split())
    s = input()
    x = 0
    index = 0
    for i in list(s):
        if x==0:
            if i == "1" and x^a[index] != 0:
                x = x ^ a[index]
                index+=1
                continue

        if x != 0:
            if i == "0" and x ^a[index]==0:
                x = x^a[index]
                index+=1
                continue
            if i == "1" and x^a[index] != 0:
                x = x ^ a[index]
                index+=1
                continue
        index+=1
    if x :
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
K=60

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

    if S=="1"*N:
        print(1)
        continue
    
    M=[]
    C=[]
    for i in range(N):
        if S[i]=="0":
            M.append(A[i])
        else:
            C.append(A[i])

    L=len(M)
    E=M+C


#E[j]>>i:i行j列

    J=0
    for k in range(L):
        i=J
        if (E[k]>>i)%2==0:
                flag=1
                for I in range(i+1,K):
                    if i!=I and (E[k]>>I)%2==1 and flag==1:
                        flag=0
                        for j in range(N):
                            p=(E[j]>>i)%2
                            q=(E[j]>>I)%2

                            if p!=q:
                                E[j]=E[j]^(1<<i)^(1<<I)
                        

        if (E[k]>>i)%2:
            J+=1
            F=[]
            for j in range(N):
                F.append((E[j]>>i)%2)
                
            for I in range(min(N,L)):
                if (i!=I) and ((E[k]>>I)%2):
                    for j in range(N):
                        E[j]^=(F[j]<<I)
        
    H=0
    for i in range(K):
        f=0
        for j in range(L):
            f=max(f,(E[j]>>i)%2)

        if f==0:
            for j in range(L,N):
                if (E[j]>>i)%2:
                    H=1

    print(H)

Submission status: Wrong Answer

Solution code:
num=int(input().rstrip())
for i in range(num):
    num_i=int(input().rstrip())
    line=input().rstrip().split()
    main=[]
    for j in range(num_i):
        main.append(int(line[j]))
    jyunnjyo=input().rstrip()
    mains=[]
    flag=0
    for k in reversed(range(num_i)):
        if main[k]%2==1:
            mains.append(k)
            flag=1
        if flag==1:
            break
    if mains==[]:
        print(0)
    else:
        print(jyunnjyo[mains[0]])
print()

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, 0] for i in range(N)]
    # 人１がビットを最後に立てた後に０にできるなら０にならない
    L = max(A).bit_length()

    res = 0
    s = [set() for i in range(L)]
    for i in range(L):
        flag = False
        for j in range(N):
            if (A[j] >> i) % 2 == 1:
                if S[j] == '0':
                    flag = False
                    s[i].add(j)
                else:
                    flag = True
                    s[i] = set()

        if flag:
            res = 1
            break
    if res or S[-1] == '1':
        print(res)
    else:
        ss = [[0, 0] for i in range(N+1)]
        for i in range(N-1, -1, -1):
            if S[i] == '0':
                ss[i][0] = ss[i+1][0] & A[i]
                ss[i][1] = ss[i+1][1]
            else:
                ss[i][1] = ss[i+1][1] & A[i]
                ss[i][0] = ss[i+1][0]

        for i in range(L):
            l = len(s[i])
            if l == 1 and ss[i][0]:
                res = 1
                break
        print(res)

Submission status: Wrong Answer

Solution code:
def kosu(kitei, aaa, tuika):
    global now_ret
    ret = 0
    n=len(kitei)
    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 now_ret==ret2:
        return 1
    else:
        if tuika==1:
            now_ret+=1
        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, 1)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer
 
t=int(input())
for i in range(t):
    now_ret=0
    n=int(input())
    alist = list(map(int, input().split()))
    s=input()

Submission status: Wrong Answer

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])
    res1 = 0
    for p11 in p1:
        res1 |= p11
    res0 = 0
    for p00 in p0:
        res0 |= p00
    bin1 = str(bin(res1))
    bin0 = str(bin(res0))
    if len(bin1) != len(bin0):
        print(1)
    else:
        flg = True
        for i in range(len(bin0)):
            if bin1[i] == 1 and bin0[i] == 0:
                flg = False
        print(0 if flg else 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
T = int(input())
# スペース区切りの整数の入力
i = 1
for i in range(T):
  N = int(input())
  A = input().split()
  S = input()
  x = 0
  for k in range(N):
    if int(S[k]) == 1 and x == 0:
      x = (x ^ int(A[k]))
    elif int(S[k]) == 0 and x != 0:
      x = (x ^ int(A[k]))
  if x == 0:
    print(0)
  elif x != 0:
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def judge(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i not in pivot:
        return False
      for j in range(cnt,len(mat)):
        if mat[j]&1<<i:
          x ^= mat[j]
          cnt = j+1
          break
  if x == 0:
    return True
  else:
    return False
def add(mat,x,pivot):
  b = x.bit_length()
  cnt = 0
  for i in range(b)[::-1]:
    if x&1<<i:
      if i in pivot:
        for j in range(cnt,len(mat)):
          if mat[j]&1<<i:
            x ^= mat[j]
            cnt = j+1
            break
      else:
        pivot.add(i)
        for j in range(len(mat)):
          if mat[j] < x:
            mat.insert(j,x)
            for k in range(i)[::-1]:
              if mat[j]&1<<k and k in pivot:
                for l in range(j+1,len(mat)):
                  if mat[l]&1<<k:
                    mat[j] ^= mat[l]
            break
        else:
          mat.append(x)
        for j in range(len(mat)):
          if mat[j] > x and mat[j]&1<<i:
            mat[j] ^= x
        break
t = int(input())
for _ in range(t):
  n = int(input())
  a = list(map(int,input().split()))
  s = input().rstrip()
  pivot = set()
  mat = []
  for i in range(n)[::-1]:
    x = a[i]
    if s[i] == "0":
      if judge(mat,x,pivot):
        continue
      else:
        add(mat,x,pivot)
    else:
      if judge(mat,x,pivot):
        continue
      else:
        print(1)
        break
  else:
    print(0)

Submission status: Wrong Answer

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])

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


def compress(string):
    """文字列をランレングス圧縮する
    例) string = "aabccaaabb" -> [(2, a), (1, b), (2, c), (3, a), (2, b)]
    """
    string = string + "#" # 番兵
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans


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

    s = compress(s)
    r = n
    memo_0 = []
    flag = False

    for turn, cnt in s[::-1]:
        tmp = xor_gauss_jordan(a[r - cnt:r])
        r -= cnt
        if turn == "1":
            for val in tmp:
                for min_ in memo_0:
                    if val & min_ == min_:
                        val -= min_
                if val != 0:
                    flag = True
        else:
            for val in tmp:
                memo_0.append(val)
                memo_0.sort(reverse=True)

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

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]
    d=[0]*60
    r=0
    f=0
    for i in range(N):
        s=bin(A[i])[2:].zfill(60)
        if S[i]:
            f=1
            s1=set([d[j] for j in range(60) if s[j]=='1'])
            s2=set([d[j] for j in range(60) if s[j]=='0'])
            if 0 in s1 or len(s1&s2):
                r=1
        else:
            if f==1:
                f=0
                d=[0]*60
            for j,c in enumerate(s):
                if c=='1':
                    d[j]+=2**i
    print(r)

Submission status: Wrong Answer

Solution code:
def main(n,a,s):
  #orders=0
  x=0
  x1=0
  x2=0
  for orders in range(n):
    man = s[orders]
    amn = a[orders]
    if man=="0":
      if x ^ amn == 0:
        x=0
      if x1 ^ amn == 0 and x1 >0:
        x1=0
      if x2 ^ amn == 0:
        x2=0
      elif x2> 0:
        x2 = x2 ^ amn
    else:
      notzero = x ^ amn
      if  notzero >0 :
        x=notzero
      notzero = x1 ^ amn
      if  x1==0 and notzero >0 :
        x1=notzero
      notzero = x2 ^ amn
      if  x2 == 0:
        x2=notzero
  if x1 + x2 + x < 2:
    print(0)
  else:
    print(1)
    
t=int(input())
for i in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  main(n,a,s)

Submission status: Wrong Answer

Solution code:
K=60

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

    if S=="1"*N:
        print(1)
        continue
    
    M=[]
    C=[]
    for i in range(N):
        if S[i]=="0":
            M.append(A[i])
        else:
            C.append(A[i])

    L=len(M)
    E=M+C


#E[j]>>i:i行j列

    J=0
    for k in range(L):
        i=J
        if (E[k]>>i)%2==0:
                flag=1
                for I in range(i+1,K):
                    if i!=I and (E[k]>>I)%2==1 and flag==1:
                        flag=0
                        for j in range(N):
                            p=(E[j]>>i)%2
                            q=(E[j]>>I)%2

                            if p!=q:
                                E[j]=E[j]^(1<<i)^(1<<I)
                        

        if (E[k]>>i)%2:
            J+=1
            F=[]
            for j in range(N):
                F.append((E[j]>>i)%2)
                
            for I in range(min(K,L)):
                if (i!=I) and ((E[k]>>I)%2):
                    for j in range(N):
                        E[j]^=(F[j]<<I)
        
    H=0
    for i in range(K):
        f=0
        for j in range(L):
            f=max(f,(E[j]>>i)%2)

        if f==0:
            for j in range(L,N):
                if (E[j]>>i)%2:
                    H=1

    print(H)

Submission status: Wrong Answer

Solution code:
t = int(input())
try_arr = []
for i in range(t):
    n = int(input())
    a = input().split()
    s = str(input())
    x = bin(0)
    try_arr.append([n,a,s,x])
for arr in try_arr:
    for i in range(arr[0]):
        if arr[2][i] == '0':
            # xが0じゃ無いかつ、排他論理和が0になる場合はxを0に変えてやる
            if arr[3] != bin(0) and bin(int(arr[3], 2) ^ int(arr[1][i])) == bin(0):
                arr[3] = bin(int(arr[3], 2) ^ int(arr[1][i]))
            else:
                pass
        else:
            if arr[3] == bin(0) or bin(int(arr[3], 2) ^ int(arr[1][i])) != bin(0):
                arr[3] = bin(int(arr[3], 2) ^ int(arr[1][i]))
            # 次の番号が0か1で対応が変わる
            else:
                if len(arr[1]) != i+1 and arr[2][i+1] == '0':
                    if bin(int(arr[3], 2) ^ int(arr[1][i])) != bin(0) and bin(int(arr[3], 2) ^ int(arr[1][i + 1])) == bin(0):
                        arr[3] = bin(int(arr[3], 2) ^ int(arr[1][i]))
                else:
                    pass
    if arr[3] == bin(0):
        print('0')
    else:
        print('1')

Submission status: Wrong Answer

Solution code:
def kosu(kitei, aaa, tuika):
    global now_ret
    ret = 0
    n=len(kitei)
    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 now_ret==ret2:
        return 1
    else:
        if tuika==1:
            now_ret+=1
        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, 1)>0:
                pass
            else:
                kitei.append(now)
        else:
            if kosu(kitei, now, 0)>0:
                pass
            else:
                answer=1
        #print(kitei)
    return answer

now_ret=0

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


def compress(string):
    """文字列をランレングス圧縮する
    例) string = "aabccaaabb" -> [(2, a), (1, b), (2, c), (3, a), (2, b)]
    """
    string = string + "#" # 番兵
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans


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

    s = compress(s)
    r = n
    memo_0 = []
    flag = False

    for turn, cnt in s[::-1]:
        tmp = xor_gauss_jordan(a[r - cnt:r])
        r -= cnt
        if turn == "1":
            for val in tmp:
                for min_ in memo_0:
                    if val & min_ == min_:
                        val -= min_
                if val != 0:
                    flag = True
        else:
            for val in tmp:
                memo_0.append(val)
                memo_0 = xor_gauss_jordan(memo_0)
                memo_0.sort(reverse=True)

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

Submission status: Wrong Answer

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 solve2(N, A, S):
  x = 0
  x2 = 0
  cand0 = []
  cand1 = []
  for i in range(N):
    x2 = int(bin(x ^ A[i]),2)
    #print("x2", x2, popcount(x2))
    #print("x", x, popcount(x))
    num = len(bin(x2)) -2
    for j in range(num):
      if x2>> j & 1:
        if S[i] == 1:
          cand1.append(j)
        else:
          cand0.append(j)
        
  cand1 = set(cand1)
  cand0 = set(cand0)
  #print("c",cand1, cand0)
  #print("c",cand1 - cand0)
  for c1 in cand1:
    if c1 not in cand0:
      print(1)
  print(0)

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 popcount(x2) < popcount(x):
        x = x2
  if x == 0:
    solve2(N,A,S)
  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: Wrong Answer

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=10))
    a1 = set(choices(list(set(al[1])), k=10))
    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: Wrong Answer

Solution code:
r =[]
T = int(input())

for i in range(T):
    N = int(input())
    A = list(map(int,input().split())) 
    S = list(map(int,input()))
    x = 0
    A_1 = list(map(lambda x: x % 2, A))
    
    for i in range(len(S)):
        
        if S[i] == 0:
            if A_1[i] == x:
                x =0
            else:
                x =x
                

        elif S[i] == 1:
            if not A_1[i] == x:
                x = 1
            else:
                x =x
    r.append(x)
for i in range(T):
    print(r[i])

Submission status: Wrong Answer

Solution code:
T=int(input())
for _ in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()
    check=[0]*60
    for i in range(N):
        if S[i]=="0":
            a=A[i]
            for j in range(60):
                if a<=0:
                    break
                b=a%2
                a//=2
                if b==1:
                    check[j]=1
        else:
            a=A[i]
            for j in range(60):
                if a<=0:
                    break
                b=a%2
                a//=2
                if b==1:
                    check[j]=-1
    ans=True
    for i in range(60):
        if check[i]<0:
            ans=False
            break
    
    if ans:
        print(0)
    else:
        print(1)