← 返回题目列表

Codeforces · 1077/D

D. 剪出

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$s$$$。

你必须找到任何长度为$$$k$$$的数组$$$t$$$,这样你就可以从数组$$$s$$$中删除数组$$$t$$$的最大副本数。

删除 $$$t$$$ 的副本意味着对于数组 $$$t$$$ 的每个元素 $$$t_i$$$,您必须在 $$$s$$$ 中找到 $$$t_i$$$ 并将其从 $$$s$$$ 中删除。如果对于某些$$$t_i$$$,你在$$$s$$$中找不到这样的元素,那么你就不能再剪出$$$t$$$的一份副本。这两个数组都可以包含重复的元素。

例如,如果 $$$s = [1, 2, 3, 2, 4, 3, 1]$$$ 且 $$$k = 3$$$,则可能的答案之一是 $$$t = [1, 2, 3]$$$。该数组 $$$t$$$ 可以被剪切 $$$2$$$ 次。

- 要剪切 $$$t$$$ 的第一个副本,您可以使用元素 $$$[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$$$ (使用突出显示的元素)。删除 $$$t$$$ 的第一个副本后,数组 $$$s$$$ 可能看起来像 $$$[1, 3, 2, 4]$$$。
- 要剪切 $$$t$$$ 的第二个副本,您可以使用元素 $$$[\underline{\textbf{1}}, \underline{\textbf{3}}, \underline{\textbf{2}}, 4]$$$。删除 $$$t$$$ 的第二个副本后,数组 $$$s$$$ 将是 $$$[4]$$$。

你的任务是找到这样的数组$$$t$$$,你可以从$$$s$$$中最大次数地剪切出$$$t$$$的副本。如果有多个答案,您可以选择其中一个。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 分别是 $$$s$$$ 中的元素数量和 $$$t$$$ 中所需的元素数量。

输入的第二行恰好包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 2 \cdot 10^5$$$)。

输出

打印 $$$k$$$ 整数 — 数组 $$$t$$$ 的元素,以便您可以从 $$$s$$$ 中删除该数组的最大可能副本数。如果有多个答案,请打印其中任何一个。所需的数组 $$$t$$$ 可以包含重复元素。 $$$t$$$ ($$$t_1, t_2, \dots, t_k$$$) 的所有元素应满足以下条件:$$$1 \le t_i \le 2 \cdot 10^5$$$。

示例

输入 #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

注意

The first example is described in the problem statement.

在第二个示例中,唯一的答案是 $$$[7, 3, 1, 3]$$$ 及其任何排列。可以证明,您不能选择任何其他数组,使得您可以剪切的最大副本数等于 $$$2$$$。

在第三个示例中,数组 $$$t$$$ 可以被剪切 $$$5$$$ 次。