/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
長さ 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 より辞書順で小さいとは、二つの数列が異なり、かつ i を x_i \neq y_i であるような最小の整数としたとき x_i < 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 通りです。
- A の 1, 3 番目の要素を選び、\{ 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 個の要素を選んで数列を作る方法は次の 3 通りです。
- A の 1, 2 番目の要素を選び、\{ 3, 1\} とする。
- A の 1, 3 番目の要素を選び、\{ 3, 4\} とする。
- A の 2, 3 番目の要素を選び、\{ 1, 4\} とする。
よって、\{ 1, 4\} を出力してください。
入力例 4
4 2 2 3 6 5 5
出力例 4
3 5
数列 A は \{ 3, 6, 5, 5\} です。D = 2 の下で、K = 2 個の要素を選んで数列を作る方法は次の 3 通りです。
- A の 1, 3 番目の要素を選び、\{ 3, 5\} とする。
- A の 1, 4 番目の要素を選び、\{ 3, 5\} とする。
- A の 2, 4 番目の要素を選び、\{ 6, 5\} とする。
よって、\{ 3, 5\} を出力してください。
Score : 6 points
Warning
Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have an integer sequence of length N: A_1, A_2, \cdots, A_N. Consider choosing K of its elements and arrange them in a row to form a new sequence without changing the relative order of the elements. Here, choosing A_i and A_j (i \neq j) at the same time is only allowed when |i - j| \geq D.
Find the lexicographically smallest sequence obtained in this way. If it is impossible to obtain a sequence in this way, print -1.
Here, a sequence of length K: x_1,x_2,\cdots,x_K is said to be lexicographically smaller than another sequence y_1,y_2,\cdots,y_K if and only if the sequences are different and x_i < y_i holds for the minimum integer i such that x_i \neq y_i.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K D A_1 A_2 \cdots A_N
Output
If it is possible to obtain a sequence in the way described in Problem Statement, print the lexicographically smallest such sequence; otherwise, print -1.
Sample Input 1
3 2 2 3 1 4
Sample Output 1
3 4
A = \{ 3, 1, 4\}. Under D = 2, there is one way to choose K = 2 elements to form a sequence, as follows:
- Choose the 1-st and 3-rd elements of A to form \{ 3, 4\}.
Thus, we should print \{ 3, 4\}.
Sample Input 2
3 3 2 3 1 4
Sample Output 2
-1
A = \{ 3, 1, 4\}. Under D = 2, there is no way to choose K = 3 elements to form a sequence.
Thus, we should print -1.
Sample Input 3
3 2 1 3 1 4
Sample Output 3
1 4
A = \{ 3, 1, 4\}. Under D = 1, there are three ways to choose K = 2 elements to form a sequence, as follows:
- Choose the 1-st and 2-nd elements of A to form \{ 3, 1\}.
- Choose the 1-st and 3-rd elements of A to form \{ 3, 4\}.
- Choose the 2-nd and 3-rd elements of A to form \{ 1, 4\}.
Thus, we should print -1.
Sample Input 4
4 2 2 3 6 5 5
Sample Output 4
3 5
A = \{ 3, 6, 5, 5\}. Under D = 2, there are three ways to choose K = 2 elements to form a sequence, as follows:
- Choose the 1-st and 3-rd elements of A to form \{ 3, 5\}.
- Choose the 1-st and 4-th elements of A to form \{ 3, 5\}.
- Choose the 2-nd and 4-th elements of A to form \{ 6, 5\}.
Thus, we should print \{ 3, 5\}.