AT_past202004_l 辞書順最小

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_l 長さ $ 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\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ D $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

操作が可能であれば得られる辞書順最小の数列を、不可能であれば $ -1 $ を出力せよ。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力は全て整数 ### Sample Explanation 1 数列 $ A $ は $ \{\ 3,\ 1,\ 4\} $ です。$ D\ =\ 2 $ の下で、$ K\ =\ 2 $ 個の要素を選んで数列を作る方法は次の $ 1 $ 通りです。 - $ A $ の $ 1,\ 3 $ 番目の要素を選び、$ \{\ 3,\ 4\} $ とする。 よって、$ \{\ 3,\ 4\} $ を出力してください。 ### Sample Explanation 2 数列 $ A $ は $ \{\ 3,\ 1,\ 4\} $ です。$ D\ =\ 2 $ の下で、$ K\ =\ 3 $ 個の要素を選んで数列を作ることはできません。 よって、$ -1 $ を出力してください。 ### Sample Explanation 3 数列 $ 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\} $ を出力してください。 ### Sample Explanation 4 数列 $ 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\} $ を出力してください。