← 返回题目列表

AtCoder · past202004_l

L. 按字典顺序最小

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

分数: 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\}.