Renako Amaori and XOR Game (hard version)

Let

$A = a_1 \oplus a_2 \oplus \cdots \oplus a_n$

and

$B = b_1 \oplus b_2 \oplus \cdots \oplus b_n.$

At index $i$, swapping $a_i$ and $b_i$ changes Ajisai's XOR by

$a_i \oplus b_i,$

and it changes Mai's XOR by the exact same value. So if the total XOR of all swapped index-differences is $S$, the final scores are

$A' = A \oplus S,$

$B' = B \oplus S.$

That means

$A' \oplus B' = A \oplus B.$

So the set of bits where the two final scores differ is fixed forever. The players can wiggle the numbers around, but they cannot change where the comparison is decided.

If $A = B$

Then $A \oplus B = 0$, and after any sequence of swaps we still have $A' = B'$.

Answer: Tie.

Now suppose $A \ne B$

Let $k$ be the highest bit where $A$ and $B$ differ. This is the only bit that matters for deciding which final score is larger. Higher bits are equal, and lower bits are irrelevant.

So:

• if bit $k$ of $A'$ is $1$, Ajisai wins;
• if bit $k$ of $A'$ is $0`, Mai wins.

A swap at index $i$ toggles bit $k$ of $A'$ exactly when bit $k$ of

$a_i \oplus b_i$

is $1$.

All other indices are useless for deciding the winner. Decorative nonsense, basically.

Now focus only on indices where $(a_i \oplus b_i)$ has bit $k$ set. Each such turn gives its owner one choice: flip the deciding bit, or don't.

The key observation: among these relevant indices, the player who owns the last one completely controls the final deciding bit.

Why? Before that last relevant move, the deciding bit has some value. On that last move, the player may either pass and keep it, or swap and flip it. Therefore they can force whichever final value they want.

Ajisai wants bit $k$ of $A'$ to be $1$. Mai wants it to be $0`.

So:

• if the last relevant index is odd, Ajisai controls it and wins;
• if the last relevant index is even, Mai controls it and wins.

There must be at least one relevant index because $k$ is set in

$A \oplus B = \bigoplus_i (a_i \oplus b_i).$

So the algorithm is:

1. Compute $A$ and $B$.
2. If $A = B$, print Tie.
3. Find the highest set bit $k$ of $A \oplus B$.
4. Find the largest index $i$ where $(a_i \oplus b_i)$ has bit $k$ set.
5. Odd index means Ajisai, even index means Mai.

Remember the statement uses 1-indexing. In C++, index 0 is turn 1, so i % 2 == 0 means Ajisai.

Time complexity: $O(n)$ per test case.

Memory complexity: $O(n)$ with stored arrays.