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:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba
import math

def run():
    T = int(input())
    for i in range(T):
        N = int(input())
        A = list(map(int, sysread().split()))
        S = list(input())
        #print(A, S)
        maxbit = math.ceil(math.log2(max(A)))
        ok = True
        selected = {i : [] for i in range(N)}
        for shift in range(maxbit):
            for index in range(N-1, -1, -1):
                #print('shift', shift, 'index',index)
                if (A[index] >> shift) % 2:
                    selected[index].append(shift)
                    if S[index] == '1':
                        #print('1st false', index, shift)
                        ok = False
                        break
                    else:
                        break
            if not ok:
                break
        if not ok:
            print(1)
        else:
            #print(selected)
            for index in range(N):
                if not ok:
                    break
                if len(selected[index]) > 0:
                    done = [0] * len(selected[index])
                    for i in range(index - 1, -1, -1):
                        if 0 not in done:
                            break
                        vals = []
                        for kk, shif in enumerate(selected[index]):
                            vals.append((A[i] >> shif) % 2)
                            if (A[i] >> shif) % 2:
                                done[kk] = 1
                        if 1 in vals and 0 in vals and S[i] == '1':
                            ok = False
                            break
            if not ok:
                print(1)
            else:
                print(0)

if __name__ == "__main__":
    run()

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 = sweep(A[left:i] + list(B0))

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
t=int(input())
def split(word): 
    return [char for char in word] 
for _ in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=str(input())
  finalsay=[]
  for i in range(n):
    finalsay.append([])
  m=[]
  for i in range(n):
    k=split('{0:b}'.format(a[i]))
    k.reverse()
    for j in range(70-len(k)):
      k.append('0')
    k.reverse()
    m.append(k)
  finallist=[-1]*70
  for i in range(70):
    for j in range(n):
      if m[n-1-j][i]=='1':
        finallist[i]=n-1-j
        break
  failflag=0
  sums=[]
  for i in range(n):
    sums.append([])
    value=0
    for j in range(70):
      value+=int(m[i][j])
      sums[i].append(value)
  for i in range(70):
    if finallist[i]==-1:
      continue
    if s[finallist[i]]=='1':
      failflag=1
      break
    else:
      finalsay[finallist[i]].append(i)
  if failflag==1:
    print(1)
    continue
  for i in range(69):
    for j in range(i+1,70):
      for l in range(n):
        if (sums[n-1-l][j]-sums[n-1-l][i]%2)==1:
          if s[n-1-l]=='1':
            failflag=1
          break
  if failflag==1:
    print(1)
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

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

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

    ans = 0
    for bit in range(64):
        msk = 1<<bit
        se0 = set([0])
        se1 = set([0])
        for i in range(N-1, -1, -1):
            if S[i] == '0':
                nxt = set()
                for k in se0:
                    nxt.add(k&msk)
                    nxt.add((k^A[i])&msk)
                se0 = nxt
            else:
                nxt = set()
                for k in se1:
                    nxt.add(k&msk)
                    nxt.add((k^A[i])&msk)
                se1 = nxt
            for k in se1:
                if k not in se0:
                    ans = 1
                    break
            if ans:
                break
        if ans:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def hatt(my_list):
  count = 0
  for i in my_list:
    count = count ^ i
  return(count)

ans = []
T = int(input())
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  # x = 0
  
  list_0 = [A[i] for i in range(N) if S[i] == '0']
  list_1 = [A[i] for i in range(N) if S[i] == '1']
  # print(list_0)
  # print(list_1)

  result_0 = []
  for n in range(len(list_0) + 1):
    for comb in itertools.combinations(list_0, n):
      result_0.append(hatt(comb))
  nums_0 = set(result_0)

  result_1 = []
  for n in range(len(list_1) + 1):
    for comb in itertools.combinations(list_1, n):
      result_1.append(hatt(comb))
  nums_1 = set(result_1)
  
  ans.append(0 if sum([num not in nums_0 for num in nums_1]) else 1)

for i in ans:
  print(ans[i])

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(str,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:
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  notzero >0:
        x2=notzero
  if x1 + x2 + x < 3:
    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:
import sys
def input():
	return sys.stdin.readline()[:-1]

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


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0



#values = [1, 5, 8, 2, 10]
#eliminated_values = eliminate(values)
#print(eliminated_values)
#x = int(input())
#print(in_span(x, eliminated_values))

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
			elim = eliminate(values)
		else:
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)

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  notzero >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:
from random import randint
t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    if s[-1]=="1":
        print(1)
        continue
    print(randint(0,1))

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

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 = sweep(A[left:i] + list(B0))

                left = i

            pre = s

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

        return 0

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from functools import reduce

def solve():
    n = int(input())#length of n
    a = list(map(int, input().split()))
    s = list(map(int, input().strip()))
    res = 0
    for i in range(n):
        if s[i] == 1:
            if res != a[i]:
                res ^= a[i]
        if s[i] == 0:
            if res == a[i]:
                res ^= a[i]
    if res != 0:
        print("1")
    else:
        print("0")

t = int(input())
for i in range(t):
    solve()

Submission status: Wrong Answer

Solution code:
t = int(input())
l = [list(map(int,input().split())) for _ in range(t*3)]

ans=[]
n = []
a = []
s = []
#n,a,sに代入
for i in range(t*3):
    if i%3==0:
        n.append(l[i]) 
    if i%3==1:
        a.append(l[i]) 
    if i%3==2: # ｓに代入しつつ文字列に置き換え
        s.append(l[i])
for m in range(t):
    for j in range(n[m][0]):
        x=1
        x =a[m][j] ^ x
    ans = format(x, 'b')
    if ans[-1]=="0":
        print("0")
    if ans[-1]!="0":
        print("1")

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  notzero >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:
T = int(input())
lines = []
line_num = 0
x = 0
for t in range(T):
  for n in range(3):
    lines.append(input())
for t in range(T):
  N = int(lines[line_num])
  line_num += 1
  a = lines[line_num].split(" ")
  A = []
  for item in a:
    A.append(int(item))
  line_num += 1
  S = lines[line_num]
  line_num += 1
  for n in range(N):
    if S[n] == "0":
      if x != 0 or x ^ A[n] == 0:
      	x = x ^ A[n]
    elif S[n] == "1":
      if x == 0 or x ^ A[n] != 0:
      	x = x ^ A[n]
  if x == 0:
    print("0")
  else:
    print("1")
  x = 0
  if len(lines) <= line_num:
    break

Submission status: Wrong Answer

Solution code:
def main():
    # XOR: 0,0->0  0,1->1  1,0->1  1,1->0
    # i桁目については常にa+bとaXORbは等しい
    # 人0はxを0に、人1はxを0以外にしたい
    # x=0にできる := 100110^100110=0;xと同じ値のA[i]で操作できる
    # 人1のあるパターンで、人0がいかなるパターンでもx!=0なら1
    # 人0のあるパターンで、人1がいかなるパターンでもx=0なら0
    # S[-1]が1ならans=1
    # そうでないとき、
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        if S[-1]=='1':
            print(1)
            continue
        else:
            # player0および1の作れる和リストを作成
            arr0,arr1 = set([0]),set([0])
            for i in range(N):
                if S[i]=='0':
                    arr0 |= set([x+A[i] for x in list(arr0)])
                else:
                    arr1 |= set([x+A[i] for x in list(arr1)])
            # リスト0がリスト1を内包するならplayer0の勝ち
            # そうでないならplayer1の勝ち
            for n1 in arr1:
                flag = False
                for n0 in arr0:
                    if n0^n1==0:
                        flag = True
                if not flag:
                    print(1)
                    return
            print(0)
            
main()

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:
            print(1)
        # print("keta=",keta)

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()
 if S[N-1]==1:
  print(1)
 else:
  wa=0
  for j in range(19):
   B=[0]*N
   for i in range(N):
    if ((i >> j) & 1):
     B[i]=1
    t=N-1
    while t>=0:
     ct=0
     lst0=set()
     lst1=set()
     while ct<2 and t>=0:
      if int(S[t])==0:
       lst0.add(B[t])
       if ct==1:
        ct=2
      else:
       lst1.add(B[t])
       if ct==0:
        ct=1
      t-=1
     if len(lst0)<len(lst1) or lst0!=lst1:
      wa+=1
  if wa==0:
   print(0)
  else:
   print(1)

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(str,input()))
    x = 0
    A_1 = map(lambda x: x % 2, A)
    A_1 = list(A_1)
    
    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:
import sys
input = sys.stdin.readline
from functools import reduce
from operator import xor


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    S = input().strip()
    return N, A, S


def solve(N, A, S):
    if S[-1] == "1":
        return 1
    P = [0, 0]
    U = [set(), set()]
    for s, a in zip(S, A):
        if s == "0":
            P[0] |= int(a)
            U[0].add(a)
        elif s == "1":
            P[1] |= int(a)
            U[1].add(a)
        else:
            raise ValueError()
    if len(U[0]) < bin(P[0]).count("1") and len(U[1]) > len(U[0]):
        return 1
    return 0 if P[0] ^ P[1] == 0 else 1


if __name__ == '__main__':
    T = int(input().strip())
    for i in range(T):
        inputs = read()
        outputs = solve(*inputs)
        if outputs is not None:
            print("{}".format(outputs))

Submission status: Wrong Answer

Solution code:
def solve(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)
      return
  print(0)

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:
t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    if s[-1]=="1":
        print(1)
        continue
    a0,a1=[],[]
    for j in range(n-1,-1,-1):
        if s[j]=="0":
            a0.append(a[j])
        else:
            a1.append(a[j])
    l0,l1=len(a0),len(a1)
    for j in range(l0):
        for k in range(l0):
            if j!=k:
                a0[k]=min(a0[k],a0[j]^a0[k])
    for j in range(l1):
        for k in range(l1):
            if j!=k:
                a1[k]=min(a1[k],a1[j]^a1[k])
    for j in range(l0):
        for k in range(l0):
            if j!=k:
                a0[k]=min(a0[k],a0[j]^a0[k])
    for j in range(l1):
        for k in range(l1):
            if j!=k:
                a1[k]=min(a1[k],a1[j]^a1[k])
    a0+=[0]
    a1+=[0]
    a0=list(set(a0))
    a1=list(set(a1))
    a0.sort()
    a1.sort()
    l0,l1=len(a0),len(a1)
    for i in range(l1):
        if a1[i] not in a0:
            print(1)
            break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
T = int(input())
lines = []
line_num = 0
x = 0
for t in range(T):
  for n in range(3):
    lines.append(input())
for t in range(T):
  N = int(lines[line_num])
  line_num += 1
  a = lines[line_num].split(" ")
  A = []
  for item in a:
    A.append(int(item))
  line_num += 1
  S = lines[line_num]
  line_num += 1
  for n in range(N):
    if S[n] == "0":
      if x != 0:
      	x = x ^ A[n]
    elif S[n] == "1":
      if x == 0 or x ^ A[n] != 0:
      	x = x ^ A[n]
  if x == 0:
    print("0")
  else:
    print("1")
  x = 0
  if len(lines) <= line_num:
    break

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()
 if S[N-1]==1:
  print(1)
 else:
  wa=0
  for j in range(19):
   B=[0]*N
   for i in range(N):
    if ((i >> j) & 1):
     B[i]=1
    t=N-1
    while t>=0:
     ct=0
     lst0=set()
     lst1=set()
     while ct<2 and t>=0:
      if int(S[t])==0:
       lst0.add(B[t])
       if ct==1:
        ct=2
      else:
       lst1.add(B[t])
       if ct==0:
        ct=1
      t-=1
     for i in lst0:
      for j in lst1:
       if i in lst1:
        continue
       else:
        wa+=1
  if wa==0:
   print(0)
  else:
   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 and mat[j]&1<<i:
            mat[j] ^= x
          elif 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)
        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:
t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    if s[-1]=="1":
        print(1)
        continue
    a0,a1=[],[]
    f=False
    for j in range(n-1,-1,-1):
        if s[j]=="0":
            if not f:
                a0.append(a[j])
        else:
            f=True
            a1.append(a[j])
    l0,l1=len(a0),len(a1)
    for j in range(l0):
        for k in range(l0):
            if j!=k:
                a0[k]=min(a0[k],a0[j]^a0[k])
    for j in range(l1):
        for k in range(l1):
            if j!=k:
                a1[k]=min(a1[k],a1[j]^a1[k])
    for j in range(l0):
        for k in range(l0):
            if j!=k:
                a0[k]=min(a0[k],a0[j]^a0[k])
    for j in range(l1):
        for k in range(l1):
            if j!=k:
                a1[k]=min(a1[k],a1[j]^a1[k])
    a0+=[0]
    a1+=[0]
    a0=list(set(a0))
    a1=list(set(a1))
    a0.sort()
    a1.sort()
    l0,l1=len(a0),len(a1)
    for i in range(l1):
        if a1[i] not in a0:
            print(1)
            break
    else:
        print(0)

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':
            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]))
            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]))
            elif bin(int(arr[3], 2) ^ int(arr[1][i])) != bin(0) and len(arr[1]) != i+1 and arr[2][i+1] == '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:
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:
        print(0)

Submission status: Wrong Answer

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

  for i in range(N):
#    print(i,S[i], A[i], x)
    if S[i] == '0':
      if x == 0:
        continue
      else:
        x = x ^ A[i]
    else:
      xx = x ^ A[i]
      if xx != 0:
        x = xx
      else:
        if i == (N-1):
          if x == 0:
            x = xx
        continue        
#    print(x)
  if x == 0:
    print(0)
  else:
    print(1)