問題一覧 > 通常問題

No.3188 K-th Lexmin

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : 蜜蜂 / テスター : Mitarushi
ProblemId : 12381 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-21 18:44:36

問題文

長さ $N$ の非負整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます．
$A$ の連続部分列は $\frac{N(N + 1)}{2}$ 通りありますが，それらを辞書順に並べたとき $K$ 番目に位置する連続部分列を出力してください．

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください．

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを意味し，各テストケースは以下の形式で与えられます．
$N\ \ K$
$A_1\ \ A_2\ \ \cdots A_N$

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq \frac{N(N + 1)}{2}$
  • $1 \leq A_i \leq N$
  • 入力はすべて整数
  • $1$ つの入力ファイルにおいて $N$ の総和は $5 \times 10^5$ を超えない

出力

各テストケースについて，辞書順に並べたとき $K$ 番目に位置する連続部分列を空白区切りで出力し，最後に改行してください．

サンプル

サンプル1
入力
3
3 4
2 1 2
4 4
1 2 3 4
17 100
12 3 6 5 6 11 13 1 2 8 2 13 1 14 1 8 7
出力
2
1 2 3 4
8 2 13 1 14 1

$1$ 番目のテストケースについて，$A$ の連続部分列は $(2), (2, 1), (2, 1, 2), (1), (1, 2), (2)$ の $6$ つです．辞書順に並べると $(1), (1, 2), (2), (2), (2, 1), (2, 1, 2)$ です．これの $4$ 番目は $(2)$ です．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。