分数: 6 点
警告
2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
我们有一个长度为的整数序列 N: A_1, A_2, \cdots, A_N。考虑选择 K 其元素并将它们排列成一行以形成新的序列,而不改变元素的相对顺序。在这里,选择 仅当以下情况时才允许同时 A_i 和 A_j (i \neq j) 仅当以下情况时才允许同时 |i - j| \geq D.
找到以这种方式获得的字典顺序最小的序列。如果无法通过这种方式获得序列,则打印 -1.
这里,长度序列 K: x_1,x_2,\cdots,x_K 据说按字典顺序小于另一个序列 y_1,y_2,\cdots,y_K 当且仅当序列不同并且 x_i < y_i 适用于最小整数 i 这样 x_i \neq y_i.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq D \leq N
- 1 \leq K \leq N
- 0 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K D A_1 A_2 \cdots A_N
输出
如果可以按照问题陈述中描述的方式获得序列,则打印字典顺序最小的序列;否则,打印 -1.
示例输入 1
3 2 2 3 1 4
示例输出 1
3 4
A = \{ 3, 1, 4\}。下 D = 2,有一种方法可以选择 K = 2 元素组成一个序列,如下:
- 选择 1-st 和 3-rd 元素 A 形成 \{ 3, 4\}.
因此,我们应该打印 \{ 3, 4\}.
示例输入 2
3 3 2 3 1 4
示例输出 2
-1
A = \{ 3, 1, 4\}。下 D = 2,没有办法选择 K = 3 元素形成序列。
因此,我们应该打印 -1.
示例输入 3
3 2 1 3 1 4
示例输出 3
1 4
A = \{ 3, 1, 4\}。下 D = 1,有三种方式可供选择 K = 2 元素组成一个序列,如下:
- 选择 1-st 和 2-nd 元素 A 形成 \{ 3, 1\}.
- 选择 1-st 和 3-rd 元素 A 形成 \{ 3, 4\}.
- 选择 2-nd 和 3-rd 元素 A 形成 \{ 1, 4\}.
因此,我们应该打印 -1.
示例输入 4
4 2 2 3 6 5 5
示例输出 4
3 5
A = \{ 3, 6, 5, 5\}。下 D = 2,有三种方式可供选择 K = 2 元素组成一个序列,如下:
- 选择 1-st 和 3-rd 元素 A 形成 \{ 3, 5\}.
- 选择 1-st 和 4第一个元素 A 形成 \{ 3, 5\}.
- 选择 2-nd 和 4第一个元素 A 形成 \{ 6, 5\}.
因此,我们应该打印 \{ 3, 5\}.