1077D. D. Cutting Out

CF1077D. Cutting Out

时限: 3 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

给你一个序列 $s$，长度为 $n$.

你需要找到一个长度为 $k$ 的序列 $t$ 使得它能被最多次数地从 $s$ 中切割。

一次切割的意思是你需要对于 $t$ 序列中所有 $t_i$，在 $s$ 中找到一个跟它相同的数，并将其移除。

举例，如果 $s=[1,2,3,2,4,3,1]$，$k=3$，那么一种可行的方案是 $t=[1,2,3]$，这个子序列可以被切割两次。

• 第一次切割，你可以选择 $[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$，移除完后 $s=[1,3,2,4]$；
• 第二次切割，你可以选择 $s=[\underline{\textbf{1}},\underline{\textbf{3}},\underline{\textbf{2}},4]$，移除完后 $s=[4]$。

你的任务是找到一个序列 $t$，能最多次数地从 $s$ 中切割它。如果有多个可行的方案，只需输出任意一种。

输入格式

第一行两个整数 $n,k(1\le k\le n\le 2\times 10^5)$，表示 $s$ 序列的长度和 $t$ 序列的长度。

接下来一行 $n$ 个整数 $s_1,s_2,...,s_n(1\le s_i\le 2\times 10^5)$。

输出格式

输出 $k$ 个整数，表示你找到的序列 $t$ 使得能被切割的次数最大。如果有多个方案，只需输出任意一种。

样例解释

第一个样例在样例描述中已经说过。

第二个样例中可行的方案只有 $[7,3,1,3]$ 和它的全排列。可以证明你不能找到其它长度为 $k$ 的序列 $t$ 使得能被切割两次

第三个样例中 $t=[1,1]$ 可以被切割五次。

样例输入 1

7 3
1 2 3 2 4 3 1

样例输出 1

1 2 3

样例输入 2

10 4
1 3 1 3 10 3 7 7 12 3

样例输出 2

7 3 1 3

样例输入 3

15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1

样例输出 3

1 1

提示

第一个样例已在题目描述中说明。

第二个样例中，唯一答案是 $[7, 3, 1, 3]$ 及其任意排列。可以证明，你无法选择其他数组使得最多能切割的次数达到 $2$。

第三个样例中，数组 $t$ 可以被切割 $5$ 次。