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:
import sys
from copy import deepcopy

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


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:
import sys
from copy import deepcopy

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


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:
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 = [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:
import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    L = len(Nums)
    index = 0
    bit = []
    for i in reversed(range(60)):
        flag = 0
        for j in range(index, L):
            if Nums[j] & (1 << i) == (1 << i):
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit.append(i)
                break
        if flag:
            for j in range(L):
                if Nums[j] & (1 << i) == (1 << i) and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1
    final_bit = []
    for i in range(index):
        if (1 << bit[i]) == Nums[i]: final_bit.append(bit[i])
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i not in final_bit: return False
    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:
t=int(input())
def solve():
    n=int(input())
    a=[int(_) for _ in input().split()]
    s=input()
    t0=[[0 for i in range(60)]for j in range(60)]
    t1=[[0 for i in range(60)]for j in range(60)]
    for i in reversed(range(n)):
        _s=bin(a[i])[2:]
        _s="0"*(60-len(_s))+_s
        if s[i]=='0':
            for j in range(60):
                for k in range(j,60):
                    if t0[j][k]==2:
                        break
                    if _s[j] != _s[k]:
                        t0[j][k]=2
                    elif _s[j]=='1':
                        t0[j][k]=max(1,t0[j][k])
                        
        else:
            for j in range(60):
                for k in range(j,60):
                    if t1[j][k]==2:
                        break
                    if _s[j] != _s[k]:
                        t1[j][k]=2
                        if t1[j][k]>t0[j][k]:
                          #  print(t1[j][k],t0[j][k],j,k,_s[j],_s[k],_s)
                            return '1'
                        
                    elif _s[j]=='1':
                        t1[j][k]=max(1,t0[j][k])
                        if t1[j][k]>t0[j][k]:
                            return '1'
        #print(_s,s[i])
    return '0'

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

Submission status: 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 and x!= 1:
        print("1")
    else:
        print(x)

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]=="1":
        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(min(K,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(K):
                if (i!=I) and ((E[k]>>I)%2):
                    for j in range(N):
                        E[j]^=(F[j]<<I)
        
    p=0
    while 0 in E[:L]:
        p+=1
        E.remove(0)

    H=0   
    for i in range(K):
        f=0
        for j in range(L-p):
            f=max(f,(E[j]>>i)%2)

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

    print(H)

Submission status: Wrong Answer

Solution code:
print("pardon me")

Submission status: Wrong Answer

Solution code:
t = int(input())
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
        for j in range(len(z2)):
            if(not(z2[j] in z1)):
                cmp = 1
                break
    else:
        cmp = 1
    print(cmp)

Submission status: Wrong Answer

Solution code:
t = int(input())
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(len(z2)):
            if(not(z2[j] in z1)):
                cmp = 1
                break
    else:
        cmp = 1
    print(cmp)

Submission status: Wrong Answer

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=6
    


    
    def pipo(x):
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        #後ろから見ていき，S=0の数だけで作れない数が(S=1の時に)出てきたらNG
        Vec=[]
        flag=1
        for i in range(N-1,-1,-1):
            #print(i,S[i]) 
            if S[i]=="0":
                if Vec==[]:
                    Vec.append((A[i],pipo(A[i])))
                else:
                    now=A[i]
                    p=pipo(A[i])
                    for v in Vec:
                        if v[1]==p:
                            now=now^v[0]
                            p=pipo(now)
                    if now!=0:
                        Vec.append((now,pipo(now)))
                        Vec.sort(reverse=True)
                            
                
            else:
                #print(Vec)
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Submission status: Wrong Answer

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=6
    


    
    def pipo(x):
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        #後ろから見ていき，S=0の数だけで作れない数が(S=1の時に)出てきたらNG
        Vec=[]
        flag=1
        for i in range(N-1,-1,-1):
            #print(i,S[i]) 
            if S[i]=="0":
                if Vec==[]:
                    Vec.append((A[i],pipo(A[i])))
                else:
                    now=A[i]
                    p=pipo(A[i])
                    for v in Vec:
                        if v[1]==p:
                            now=now^v[0]
                    if now!=0:
                        Vec.append((now,pipo(now)))
                        Vec.sort(reverse=True)
                            
                
            else:
                #print(Vec)
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Submission status: Wrong Answer

Solution code:
t = int(input())
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:
def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        a = [int(j) for j in input().split()]
        s = input()
        x = 0
        tmp = 0
        for k in range(n):
            if s[k] == '0' and x == 1:
                tmp = x ^ a[k]
                if tmp == 0:
                    x = tmp
            elif s[k] == '1' and x == 0:
                tmp = x ^ a[k]
                if tmp == 1:
                    x = tmp
        print(f'{x}')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    M=6
    


    
    def pipo(x):
        cnt=0
        for i in range(M):
            if x==0:
                return cnt
            else:
                x=x//2
                cnt+=1
    

        
    
    for _ in range(T):
        N=I()
        A=LI()
        S=list(input())
        if S[-1]=="1":
            flag=0
            break
        #後ろから見ていき，S=0の数だけで作れない数が(S=1の時に)出てきたらNG
        Vec=[]
        cnt=1
        flag=1
        for i in range(N-1,-1,-1):
            #print(i,S[i]) 
            if S[i]=="0":
                if Vec==[]:
                    Vec.append((A[i],pipo(A[i])))
                else:
                    now=A[i]
                    p=pipo(A[i])
                    for v in Vec:
                        if v[1]==p:
                            now=now^v[0]
                    if now!=0:
                        Vec.append((now,pipo(now)))
                        Vec.sort(reverse=True)
                            
                
            else:
                #print(Vec)
                now=A[i]
                for v in Vec:
                    if v[1]==pipo(now):
                        now=now^v[0]
                if now!=0:
                    flag=0

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

main()

Submission status: Wrong Answer

Solution code:
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:
r =[]
T = int(input())
x = 0
for i in range(T):
    N = int(input())
    A = list(map(int,input().split())) 
    S = list(map(int,input()))
    
    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:
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:
        import random
        z = random.random()
        print(int(2*z))

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

    if N > 20:
        A = A[N-20:]
        S = S[N-20:]
        N = 20

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

    return f(0, 0)

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

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

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


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

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

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


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


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

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


    #     # A = [4, 16, 2, 10, 3, 13, 6, 4, 1, 3]
    #     # S = ['0', '0', '1', '0', '0', '0', '0', '0', '0', '0']
    #     # print(A)
    #     # print(S)
    #     a = ref(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:
print("I COULDN'T SOLVE THIS PROBLEM!!!")

Submission status: Wrong Answer

Solution code:
print()

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:
            # xが0の場合かつ排他論理和が0じゃ無い時
            if arr[3] == bin(0):
                arr[3] = bin(int(arr[3], 2) ^ int(arr[1][i]))
            # 次の番号が0か1で対応が変わる
            else:
                # 0じゃ無い場合
                # if  bin(int(arr[3], 2) ^ int(arr[1][i])) != bin(0):
                #     arr[3] = bin(int(arr[3], 2) ^ int(arr[1][i]))
                if len(arr[1]) != i+1 and arr[2][i+1] == '0' and bin(int(arr[3], 2) ^ int(arr[1][i])) != bin(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:
import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def rec(i, cur):
    if memo[i][cur] != -1:
        return memo[i][cur]
    if i == N:
        if cur == 0:
            return 0
        else:
            return 1
    if S[i] == '0':
        res = 1
        res &= rec(i+1, cur&msk)
        res &= rec(i+1, cur^A[i]&msk)
    else:
        res = 0
        res |= rec(i+1, cur&msk)
        res |= rec(i+1, cur^A[i]&msk)
    memo[i][cur] = res
    return res

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()

    for k in range(64):
        msk = 1<<k
        memo = [defaultdict(lambda: -1) for i in range(N+1)]
        ans = rec(0, 0)
        if ans:
            print(1)
            break
    else:
        print(0)

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

        pre = '-1'
        left = 0
        for i, s in enumerate(S):
            if s != pre and i != 0:
                if s == '0':
                    B1 = sweep(A[left:i])
                    for b1 in B1:
                        for b0 in B0:
                            if b1 & b0 == b0:
                                b1 ^= b0
                        if b1:
                            return 1
                else:
                    B0 = B0 | sweep(A[left:i])

                left = i

            pre = s

        if pre == '1':
            B1 = sweep(A[left:])
            for b1 in B1:
                for b0 in B0:
                    if b1 & b0 == b0:
                        b1 ^= b0
                if b1:
                    return 1

        return 0

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


if __name__ == '__main__':
    main()