問題一覧 > 通常問題

No.2210 equence Squence Seuence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 127
作問者 : ShirotsumeShirotsume / テスター : 👑 p-adicp-adic 👑 ygussanyygussany
10 ProblemId : 8750 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-08 21:53:02

問題文

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。

各 $i$ $(1 \leq i \leq N)$ について、 $A$ から $i$ 番目の要素を取り除いてできる長さ $N - 1$ の数列を $X_i$ とおきます。

$N$ 個の数列 $X_1, X_2, \dots, X_N$ を辞書順の昇順に並べたとき、 $K$ 番目となる数列を求めてください。

辞書順とは(クリックで展開)

長さが $L$ である $2$ つの相異なる数列 $X, \ Y$ が与えられたとき、 $X$ と $Y$ の辞書順による大小は以下のように決まります。

  • $X_i \neq Y_i$ なる $i$ $(1 \leq i \leq L)$ のうち最小の $i$ を $j$ とする。 $X_j < Y_j$ ならば $X < Y$ 、 $X_j > Y_j$ ならば $X > Y$ と決定する。

制約

  • 入力は全て整数
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq N$
  • $1 \leq A_i \leq N$

入力

入力は標準入力から以下の形式で与えられる。

$N$ $K$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

出力

数列 $B$ が答えであるとき、$B$ の各要素を空白区切りで出力せよ。

$B_{1}$ $B_{2}$ $\dots$ $B_{N-1}$

サンプル

サンプル1
入力
3 3
2 1 1
出力
2 1

$X_1 = (1,1), X_2 = (2,1), X_3 = (2,1)$ です。これらを辞書順の昇順に並べ替えると $(1, 1), (2, 1), (2, 1)$ になります。よって、$(2,1)$ が辞書順で小さい方から $3$ 番目になります。

サンプル2
入力
5 3
3 1 4 1 5
出力
3 1 4 1

$X_1 = (1,4,1,5), X_2 = (3,4,1,5), X_3 = (3,1,1,5), X_4 = (3,1,4,5), X_5 = (3,1,4,1)$ です。これらを辞書順の昇順に並べ替えると $(1,4,1,5), (3,1,1,5), (3,1,4,1), (3,1,4,5),(3,4,1,5)$ になります。辞書順で $3$ 番目になるのは $(3, 1, 4, 1)$ です。

サンプル3
入力
10 8
3 6 8 1 10 5 7 2 4 9
出力
3 6 8 10 5 7 2 4 9

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