P2776 [SDOI2007] Team Queue

Well, somehow this very simple NOI Qualifier problem to boost confidence isn’t on Luogu. How could such a simple problem be missing. It’s my responsibility to raise everyone’s morale. So I’m adding it here. Worth mentioning, the reference solution is my own. It’s quite weak, but since the testdata is easy, it can AC. Experts, please don’t roast me.

There are $m$ groups and $n$ elements. Each element belongs to exactly one group. Support the following operations: `push x`: Enqueue element `x`. If there is already an element from `x`’s group ahead in the queue, `x` will be placed immediately after the last element of its own group currently in the queue; otherwise, `x` will be placed at the end of the whole queue. `pop`: Dequeue. Remove the front element of the queue and output it. This behaves like a normal queue, i.e., elements in front leave first.

The first line contains two positive integers $n$, $m$, representing the number of elements and the number of groups. Elements and groups are numbered starting from $0$. The next line contains $n$ non-negative integers $A_i$, where $A_i$ is the group that element $i$ belongs to. The next line contains a positive integer $T$, the number of operations. The next $T$ lines each contain one operation.

For each dequeue operation, output the dequeued element on a separate line.

For $30\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 10$, $T \le 50$. For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le m \le 300$, $T \le 100000$. The input guarantees that all operations are valid. Translated by ChatGPT 5