問題一覧 > 通常問題

No.2210 equence Squence Seuence

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

問題文

長さ NN の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) が与えられます。

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

NN 個の数列 X1,X2,…,XNX_1, X_2, \dots, X_N を辞書順の昇順に並べたとき、 KK 番目となる数列を求めてください。

辞書順とは（クリックで展開）

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

  • Xi≠YiX_i \neq Y_i なる ii (1≤i≤L)(1 \leq i \leq L) のうち最小の ii を jj とする。 Xj<YjX_j < Y_j ならば X<YX < Y 、 Xj>YjX_j > Y_j ならば X>YX > Y と決定する。

制約

  • 入力は全て整数
  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤K≤N1 \leq K \leq N
  • 1≤Ai≤N1 \leq A_i \leq N

入力

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

NN KK
A1A_1 A2A_2 A3A_3 …\dots ANA_N

出力

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

B1B_{1} B2B_{2} …\dots BN−1B_{N-1}

サンプル

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

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

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

X1=(1,4,1,5),X2=(3,4,1,5),X3=(3,1,1,5),X4=(3,1,4,5),X5=(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)(1,4,1,5), (3,1,1,5), (3,1,4,1), (3,1,4,5),(3,4,1,5) になります。辞書順で 33 番目になるのは (3,1,4,1)(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もしくは右上の雲マークをクリックしてアカウントを作成してください。