Codeforces Round #717 AGAGA XOOORRR - bitmasks

Solution:

If the XOR sum of all numbers is 0. Then it must can make it. Because if and only if $a[1]\oplus a[2]\oplus...\oplus a[n-1]=a[n]$, the XOR sum is 0. So we can make the array as: $(a[n], a[n])$.

So the problem is what if the XOR sum is not 0.

Let's say $a[1]\oplus a[2]\oplus...\oplus a[n-1]\oplus a[n]=x$. If it can make a array which is match the requirement. Then the result must be something like: $(x,x,x,...,x)$.

So there should exist a $i$, so that $a[i]\oplus a[i+1]\oplus ... \oplus a[n-1]\oplus a[n]=x$ and $a[1]\oplus a[2]\oplus ... \oplus a[i-1]=0$.

Then the last thing is, can we make a $x$ from the last few numbers between 0 to $i-1$. If can, then can make $(x,x,x)$. Otherwise, print "No".

Code:

Submission #113893128 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge