P9283 [AGM 2023 Qualifier] Piece Game

Alice and Bob play a game on a $1 \times N$ grid. There are $M$ pieces placed on different cells, and the pieces have various colors. In each turn, a player may choose one piece, and move this piece together with the consecutive pieces after it that have different colors (i.e., all pieces before the next piece of the same color) to the left by a positive distance. During the movement, they must not cross over or overlap the cell immediately in front of them. Alice moves first, and the player who cannot make a move loses. Then there are $Q$ operations. Each operation is in one of the following forms: 1: Place a piece of color $col$ at position $pos$. 2: Remove the piece at position $pos$. After each operation, output who wins under the current position.

The first line contains two integers $N, M(1 \leq N \leq 10^9, 1 \leq M \leq 10^5)$. The next $M$ lines each contain two integers $pos(1 \leq pos \leq N)$ and $col(1 \leq col \leq 5)$, meaning there is initially a piece of color $col$ at position $pos$. The next $Q$ lines each contain two or three integers. The first is $opt(1 \leq opt \leq 2)$, indicating the operation type, followed by $pos(1 \leq pos \leq N)$. If $opt = 1$, then an additional integer $col(1 \leq col \leq 5)$ is given.

Output $Q$ lines. Each line should be either Alice or Bob.

Translated by ChatGPT 5