No.2210 equence Squence Seuence
タグ : / 解いたユーザー数 129
作問者 :
Shirotsume
/ テスター :
👑 
p-adic
👑 
ygussany
問題文
長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。