4221. 「IOI2024」象形文字序列

时间限制：1000 ms
内存限制：2048 MiB
通过：19
提交：139

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "hieroglyphs.h"。

题目描述

一个研究团队正在研究象形文字序列之间的相似性。他们将每个象形文字表示成一个非负整数。为了开展研究，他们采用了关于序列的如下概念。

对于一个给定的序列 $A$，某个序列 $S$ 被称为是 $A$ 的子序列，当且仅当 $S$ 能够通过移除 $A$ 中的某些（也可能零个）元素而得到。

下表给出了序列 $A = [3, 2, 1, 2]$ 的子序列的一部分例子。

子序列	由 $A$ 得到子序列的方式
$[3, 2, 1, 2]$	不移除任何元素
$[2, 1, 2]$	$[3, \mathbf{2}, 1, 2]$
$[3, 2, 2]$	$[3, 2, \mathbf{1}, 2]$
$[3, 2]$	$[3, 2, \mathbf{1}, \mathbf{2}]$ 或者 $[3, \mathbf{2}, 1, 2]$
$[3]$	$[3, \mathbf{2}, \mathbf{1}, \mathbf{2}]$
$[ ]$	$[\mathbf{3}, \mathbf{2}, \mathbf{1}, \mathbf{2}]$

另一方面，$[3, 3]$ 或 $[1, 3]$ 不是 $A$ 的子序列。

考虑有两个象形文字序列 $A$ 和 $B$。某个序列 $S$ 被称为是 $A$ 和 $B$ 的公共子序列，当且仅当 $S$ 同时是 $A$ 和 $B$ 的子序列。此外，我们说某个序列 $U$ 是 $A$ 和 $B$ 的一个最全公共子序列，当且仅当如下两个条件成立：

1. $U$ 是 $A$ 和 $B$ 的一个公共子序列。
2. $A$ 和 $B$ 的任意公共子序列，都是 $U$ 的一个子序列。

可以证明，任意两个序列 $A$ 和 $B$ 都至多有一个最全公共子序列。

研究人员发现了两个象形文字序列 $A$ 和 $B$。序列 $A$ 包含 $N$ 个象形文字，而序列 $B$ 包含 $M$ 个象形文字。请帮助研究人员为序列 $A$ 和 $B$ 找到一个最全公共子序列，或者判定这样的序列并不存在。

实现细节

你要实现以下函数。

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

• A：长度为 $N$ 的数组，给出第一个序列。
• B：长度为 $M$ 的数组，给出第二个序列。
• 如果 $A$ 和 $B$ 有一个最全公共子序列，该函数应当返回一个包含该序列的数组。否则，该函数应当返回 $[-1]$（一个长度为 $1$ 的数组，其唯一元素为 $-1$）。
• 对每个测试用例，该函数恰好被调用一次。

约束条件

• $1 \leq N \leq 100\,000$
• $1 \leq M \leq 100\,000$
• 对所有满足 $0 \leq i < N$ 的 $i$，都有 $0 \leq A[i] \leq 200\,000$
• 对所有满足 $0 \leq j < M$ 的 $j$，都有 $0 \leq B[j] \leq 200\,000$

子任务

子任务	分数	额外的约束条件
1	$3$	$N = M$；$A$ 和 $B$ 均由 $N$ 个不同的整数构成，取自 $0$ 到 $N-1$（包括这两个值）
2	$15$	对任意整数 $k$，$k$ 在 $A$ 和 $B$ 中的出现次数，加起来至多等于 $3$
3	$10$	对所有满足 $0 \leq i < N$ 的 $i$，都有 $A[i] \leq 1$；对所有满足 $0 \leq j < M$ 的 $j$，都有 $B[j] \leq 1$
4	$16$	$A$ 和 $B$ 存在最全公共子序列
5	$14$	$N \leq 3000$；$M \leq 3000$
6	$42$	没有额外的约束条件

例子

例 1

考虑以下函数调用。

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

此时，$A$ 和 $B$ 的公共子序列为：$[ ]$，$[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]$ 和 $[0, 1, 0, 2]$。

由于 $[0, 1, 0, 2]$ 是 $A$ 和 $B$ 的一个公共子序列，而 $A$ 和 $B$ 的所有公共子序列又都是 $[0, 1, 0, 2]$ 的子序列，因此函数应该返回 $[0, 1, 0, 2]$。

例 2

考虑以下函数调用。

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

此时，$A$ 和 $B$ 唯一的公共子序列为空序列 $[ ]$。因此函数应该返回一个空数组 $[ ]$。

例 3

考虑以下函数调用。

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

此时，$A$ 和 $B$ 的公共子序列为 $[ ]$，$[0]$，$[1]$，$[0, 1]$ 和 $[1, 0]$，可以看出两者并不存在最全公共子序列。因此，函数应该返回 $[-1]$。

评测程序示例

输入格式：

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

输出格式：

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

这里 $R$ 是 ucs 所返回的数组，而 $T$ 为其长度。