P11052 [IOI 2024] Hieroglyph Sequence

Please do not include `hieroglyphs.h` when submitting. Do not submit in C++14 (GCC 9).

A research team is studying the similarity between hieroglyph sequences. They represent each hieroglyph as a non-negative integer. For their research, they use the following concepts about sequences. For a given sequence $A$, a sequence $S$ is called a **subsequence** of $A$ if and only if $S$ can be obtained by removing some (possibly zero) elements from $A$. The table below shows some examples of subsequences of the sequence $A = [3, 2, 1, 2]$. | Subsequence | How to obtain the subsequence from $A$ | | ------------ | -------------------------------------------------------- | | [3, 2, 1, 2] | Remove no elements. | | [2, 1, 2] | [~~3~~, 2, 1, 2] | | [3, 2, 2] | [3, 2, ~~1~~, 2] | | [3, 2] | [3, ~~2~~, ~~1~~, 2] or [3, 2, ~~1~~, ~~2~~] | | [3] | [3, ~~2~~, ~~1~~, ~~2~~] | | [ ] | [~~3~~, ~~2~~, ~~1~~, ~~2~~] | On the other hand, $[3, 3]$ or $[1, 3]$ is not a subsequence of $A$. Now consider two hieroglyph sequences $A$ and $B$. A sequence $S$ is called a **common subsequence** of $A$ and $B$ if and only if $S$ is a subsequence of both $A$ and $B$. Furthermore, we say that a sequence $U$ is a **universal common subsequence** of $A$ and $B$ if and only if the following two conditions hold: * $U$ is a common subsequence of $A$ and $B$. * Every common subsequence of $A$ and $B$ is a subsequence of $U$. It can be proven that any two sequences $A$ and $B$ have at most one universal common subsequence. The researchers found two hieroglyph sequences $A$ and $B$. Sequence $A$ contains $N$ hieroglyphs, and sequence $B$ contains $M$ hieroglyphs. Please help the researchers find a universal common subsequence of $A$ and $B$, or determine that such a sequence does not exist.

``` N M A[0] A[1] ... A[N-1] B[0] B[1] ... B[M-1] ```

``` T R[0] R[1] ... R[T-1] ``` Here, $R$ is the array returned by `ucs`, and $T$ is its length.

# Description ## Implementation Details You have to implement the following function. ``` std::vector ucs(std::vector A, std::vector B) ``` * $A$: an array of length $N$, giving the first sequence. * $B$: an array of length $M$, giving the second sequence. * If $A$ and $B$ have a universal common subsequence, the function should return an array containing that sequence. Otherwise, the function should return $[-1]$ (an array of length $1$ whose only element is $-1$). * For each test case, this function is called exactly once. # Input Format ## Constraints * $1 \leq N \leq 100\,000$ * $1 \leq M \leq 100\,000$ * For all $i$ with $0 \leq i < N$, $0 \leq A[i] \leq 200\,000$ * For all $j$ with $0 \leq j < M$, $0 \leq B[j] \leq 200\,000$ ## Subtasks | Subtask | Score | Additional constraints | | :-----: | :---: | ------------------------------------------------------------ | | 1 | $3$ | $N = M$; both $A$ and $B$ consist of $N$ **distinct** integers, taken from $0$ to $N-1$ (inclusive) | | 2 | $15$ | For any integer $k$, the total number of occurrences of $k$ in $A$ and $B$ is at most $3$. | | 3 | $10$ | For all $i$ with $0 \leq i < N$, $A[i] \leq 1$; for all $j$ with $0 \leq j < M$, $B[j] \leq 1$ | | 4 | $16$ | A universal common subsequence of $A$ and $B$ exists. | | 5 | $14$ | $N \leq 3000$; $M \leq 3000$ | | 6 | $42$ | No additional constraints. | ## Examples ### Example 1 Consider the following function call. ``` ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2]) ``` In this case, the common subsequences of $A$ and $B$ are: $[\ ]$, $[0]$, $[1]$, $[2]$, $[0, 0]$, $[0, 1]$, $[0, 2]$, $[1, 0]$, $[1, 2]$, $[0, 0, 2]$, $[0, 1, 0]$, $[0, 1, 2]$, $[1, 0, 2]$, and $[0, 1, 0, 2]$. Since $[0, 1, 0, 2]$ is a common subsequence of $A$ and $B$, and all common subsequences of $A$ and $B$ are subsequences of $[0, 1, 0, 2]$, the function should return $[0, 1, 0, 2]$. ### Example 2 Consider the following function call. ``` ucs([0, 0, 2], [1, 1]) ``` In this case, the only common subsequence of $A$ and $B$ is the empty sequence $[\ ]$. Therefore, the function should return an empty array $[\ ]$. ### Example 3 Consider the following function call. ``` ucs([0, 1, 0], [1, 0, 1]) ``` In this case, the common subsequences of $A$ and $B$ are $[\ ]$, $[0]$, $[1]$, $[0, 1]$, and $[1, 0]$. We can see that a universal common subsequence does not exist. Therefore, the function should return $[-1]$. # Output Format # Hint Translated by ChatGPT 5