32267번 - Hieroglyphs 서브태스크다국어언어 제한함수 구현

문제

A team of researchers is studying the similarities between sequences of hieroglyphs. They represent each hieroglyph with a non-negative integer. To perform their study, they use the following concepts about sequences.

For a fixed sequence $A,ドル a sequence $S$ is called a subsequence of $A$ if and only if $S$ can be obtained by removing some elements (possibly none) from $A$.

The table below shows some examples of subsequences of a sequence $A = [3, 2, 1, 2]$.

On the other hand, $[3, 3]$ or $[1, 3]$ are not subsequences of $A$.

Consider two sequences of hieroglyphs, $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$. Moreover, we say that a sequence $U$ is a universal common subsequence of $A$ and $B$ if and only if the following two conditions are met:

• $U$ is a common subsequence of $A$ and $B$.
• Every common subsequence of $A$ and $B$ is also a subsequence of $U$.

It can be shown that any two sequences $A$ and $B$ have at most one universal common subsequence.

The researchers have found two sequences of hieroglyphs $A$ and $B$. Sequence $A$ consists of $N$ hieroglyphs and sequence $B$ consists of $M$ hieroglyphs. Help the researchers compute a universal common subsequence of sequences $A$ and $B,ドル or determine that such a sequence does not exist.

구현 상세

You should implement the following procedure.

std::vector<int> ucs(std::vector<int> A, std::vector<int> B)

• $A$: array of length $N$ describing the first sequence.
• $B$: array of length $M$ describing the second sequence.
• If there exists a universal common subsequence of $A$ and $B,ドル the procedure should return an array containing this sequence. Otherwise, the procedure should return $[-1]$ (an array of length 1ドル,ドル whose only element is $-1$).
• This procedure is called exactly once for each test case.

입력

출력

제한

• 1ドル ≤ N ≤ 100,円 000$
• 1ドル ≤ M ≤ 100,円 000$
• 0ドル ≤ A[i] ≤ 200,円 000$ for each $i$ such that 0ドル ≤ i < N$
• 0ドル ≤ B[j] ≤ 200,円 000$ for each $j$ such that 0ドル ≤ j < M$

서브태스크

힌트

예제 1

Consider the following call.

ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])

Here, the common subsequences of $A$ and $B$ are the following: $[ ],ドル $[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 procedure should return $[0, 1, 0, 2]$.

예제 2

Consider the following call.

ucs([0, 0, 2], [1, 1])

Here, the only common subsequence of $A$ and $B$ is the empty sequence $[ ]$. It follows that the procedure should return an empty array $[ ]$.

예제 3

Consider the following call.

ucs([0, 1, 0], [1, 0, 1])

Here, the common subsequences of $A$ and $B$ are $[ ],ドル $[0],ドル $[1],ドル $[0, 1]$ and $[1, 0]$. It can be shown that a universal common subsequence does not exist. Therefore, the procedure should return $[-1]$.

첨부

Input format:

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

Output format:

T
R[0] R[1] ... R[T-1]

Here, $R$ is the array returned by ucs and $T$ is its length.

첨부

• hieroglyphs.zip