Battle of Arrays

Comparing sums is bait. The first sample has Alice total $70$ and Bob total $90$, but Alice wins anyway. So yeah, sums are lying to your face.

The Greedy Move Is Forced

Suppose it is Alice's turn. Bob's attacked element is fixed by the statement: it must be Bob's maximum element $y$.

Alice only chooses the attack value $x$ from her own array.

If Alice has two choices $x_1 < x_2$, then using $x_2$ is always at least as good:

• Alice's own array does not change after attacking.
• Bob's maximum becomes smaller with $x_2$ than with $x_1$, or gets destroyed.
• Giving Bob a smaller array can never help Bob.

So Alice should always use her current maximum. Same exact argument applies to Bob.

This kills the scary minimax tree. The game is deterministic under optimal play: max attacks max, every turn.

Simulation

Maintain two max-heaps.

On Alice's turn:

1. Let $x$ be Alice's maximum.
2. Let $y$ be Bob's maximum.
3. Remove $y$ from Bob's heap.
4. If $y > x$, push $y - x$ back into Bob's heap.
5. If Bob's heap is empty, Alice wins.

Bob's turn is symmetric.

That is literally the whole algorithm. The only possible concern is whether this loop can run forever-ish because values go up to $10^9$. It cannot.

Why The Simulation Is Fast

Let $N = n + m$, and let $S$ be the current total sum of all alive elements.

Look at two consecutive moves.

If either move destroys an element, great. There are only $N$ elements total, so this can only happen $N$ times.

Otherwise, no element is destroyed in those two moves. Consider the first move in the pair. Let the attacker maximum be $x$, and the opponent maximum be $y$.

Since no destruction happens on the first move, we have $y > x$. That means $y$ is the global maximum at the start of the pair.

After the first move, that element becomes $y - x$. On the second move, if the attacker could destroy $x$, we would be in the deletion case. Since we are not, the second attacker's maximum is less than $x$. But it is at least $y - x$, so:

$y - x < x$

Therefore:

$x > y/2$

The first move alone decreases the total sum by $x$, which is more than half of the global maximum. Since the global maximum is at least $S/N$, the sum drops by more than:

$S/(2N)$

So every non-deleting pair of moves multiplies $S$ by at most $1 - 1/(2N)$. With total initial sum at most about $10^{14}$, this gives only $O(N \log S)$ simulated moves. No billion-turn nonsense hiding under the bed.

Correctness Proof

First, on every turn, choosing the current maximum is optimal. Replacing any smaller chosen value with the current maximum leaves the player's own array unchanged and makes the opponent's array no larger. This cannot worsen the current player's position.

Second, because both players have this same dominant choice, optimal play is exactly the heap simulation described above.

Third, the simulation applies the statement's operation exactly: it always attacks the opponent's maximum, removes it if the attack is large enough, and otherwise reinserts the decreased value.

Finally, the first player whose move empties the opponent's heap is printed as the winner, exactly matching the win condition.

Complexity

Let $N = n + m$ and $S$ be the initial total sum.

The number of simulated moves is $O(N \log S)$, and each heap operation costs $O(\log N)$.

So the total complexity is:

$O(N \log S \log N)$

This easily fits for the given limits.