D - KthLIS
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1200 点
問題文
高橋君は,長さ N の数列 A を持っています. 高橋君は,A の最長増加部分列を探して遊ぶことにしました. A の最長増加部分列とは,A の部分列であり,かつ狭義単調増加なものの中で,最も長いものを意味します. 高橋君は,A の最長増加部分列をただ探すだけではつまらないと思い,A の最長増加部分列となる部分列の中で,辞書順で K 番目のものを求めることにしました. なお,取り出す位置が異なっても,数列として同じ部分列は区別しないことにしました.
しかし,高橋くんは途中で疲れて寝てしまいました.
高橋君の代わりに,A の最長増加部分列のうち辞書順で K 番目のものを求めて出力するプログラムを書いてください.
なお,そのようなものが存在しない場合は,None
と出力してください.
制約
- 入力は全て整数である
- 1 \leq N \leq 300,000
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる.
N K A_1 A_2 ... A_N
出力
A の最長増加部分列のうち辞書順で K 番目のものを,空白を区切りとして出力せよ.
そのようなものが存在しない場合は,None
と出力せよ.
入力例 1
6 2 3 6 5 1 2 7
出力例 1
3 5 7
A の最長部分増加列となる部分列は,以下の 3 通りあります.
- [1,2,7]
- [3,5,7]
- [3,6,7]
辞書順で 2 番目のものは,[3,5,7] です.
入力例 2
4 2 1 1 2 2
出力例 2
None
A の最長増加部分列は,[1,2] の 1 通りしかないので,None
を出力します.
入力例 3
20 1000 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19
出力例 3
2 4 6 8 10 11 13 16 18 20