Minimum Permutation

题目描述

我们有一个长度为 $N$ 的序列 $A$，由介于 $1$ 到 $M$ 之间的整数构成。这里，每个整数 $1$ 到 $M$ 都至少在 $A$ 中出现过一次。 在所有长度为 $M$ 的子序列中（其中 $1, \ldots, M$ 各出现一次），找到字典序最小的一个。

输入格式

输入按照下列格式由标准输入给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设所求子序列为 $B_1, \ldots, B_M$，按如下格式输出： $B_1$ $B_2$ $\ldots$ $B_M$

4 3
2 3 1 3

2 1 3

4 4
2 3 1 4

2 3 1 4

20 10
6 3 8 5 8 10 9 3 6 1 8 3 3 7 4 7 2 7 8 5

3 5 8 10 9 6 1 4 2 7

提示

$1 \leq M \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq M$ 序列 $A$ 中每个介于 $1$ 到 $M$（含）之间的整数至少出现一次。 输入中的所有数值都是整数。序列 $A$ 的长度为 $3$ 的、包含 $1,2,3$ 各一次的子序列有 $(2, 3, 1)$ 和 $(2, 1, 3)$。其中字典序较小的是 $(2, 1, 3)$。

标签: AtCoder|abc299G

来源

AtCoder|abc299G