1516B - AGAGA XOOORRR - CodeForces Solution


bitmasks brute force dp greedy *1500

Please click on ads to support us..

Python Code:

import decimal
import heapq
import math
import os
import random
import sys
from collections import Counter, deque, defaultdict
from io import BytesIO, IOBase
import bisect
from types import GeneratorType

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True


def lcm(a, b): return (a * b) // math.gcd(a, b)


def ciel(a, b):
    x = a // b
    if a % b == 0:
        return x
    return x + 1


def ints_get(): return map(int, input().strip().split())


def list_get(): return list(map(int, sys.stdin.readline().strip().split()))


def chars_get(): return list(map(str, sys.stdin.readline().strip().split()))


def ipn(): return int(input())


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc




def main():
    for _ in range(ipn()):
        n = ipn()
        a = list_get()
        p = a[0]
        for i in range(1, n):
            p ^= a[i]
        if p == 0:
            print("YES")
        else:
            flag = 0
            q = [a[0]]
            for i in range(1, n):
                q.append(q[-1] ^ a[i])
            for i in range(1, n):
                for j in range(i, n):
                    if q[i - 1] == q[j] ^ q[i - 1] == q[-1] ^ q[j]:
                        flag = 1
                        break
                if flag:
                    print("YES")
                    break
            else:
                print("NO")
    return


if __name__ == "__main__":
    main()



C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 1e6 + 7;
typedef long long ll;
int n;
int a[N],f[N];
void process() {
    cin>>n;
    for(int i = 1; i <= n;i++) cin>>a[i];
    for(int i = 1;i <= n;i++) f[i] = f[i - 1]^a[i];
    if(f[n] == 0)
    {
        cout<<"YES"<<endl;
        return;
    }
    for(int i = 1; i <= n;i++)
    {
        if(f[i] == f[n])
        {
            int flag = 0;
            for(int j = i + 1; j < n;j++)
            if(f[j] == 0)
            {
                flag = 1;
                break;
            }
             if(flag) cout<<"YES"<<endl;
            else 
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"NO"<<endl;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test ;
    cin>>test;
    for(int i = 0; i < test;i++)
    {
        process();
    }
}


Comments

Submit
0 Comments
More Questions

Differences of the permutations
Doctor's Secret
Back to School
I am Easy
Teddy and Tweety
Partitioning binary strings
Special sets
Smallest chosen word
Going to office
Color the boxes
Missing numbers
Maximum sum
13 Reasons Why
Friend's Relationship
Health of a person
Divisibility
A. Movement
Numbers in a matrix
Sequences
Split houses
Divisible
Three primes
Coprimes
Cost of balloons
One String No Trouble
Help Jarvis!
Lift queries
Goki and his breakup
Ali and Helping innocent people
Book of Potion making