No.2210 equence Squence Seuence
タグ : / 解いたユーザー数 130
作問者 :
Shirotsume
/ テスター :
👑 
p-adic
ygussany
Problem Statement
You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$.
For each $i$ $(1 \leq i \leq N)$, let $X_i$ be the sequence of length $N - 1$ obtained by removing the $i$-th element from $A$.
Find the $K$-th sequence when the $N$ sequences $X_1, X_2, \dots, X_N$ are arranged in ascending lexicographic order.
What is lexicographic order? (click to expand)
Given $2$ distinct sequences $X, \ Y$ of length $L$, the lexicographic order between $X$ and $Y$ is determined as follows.
- Among the indices $i$ $(1 \leq i \leq L)$ such that $X_i \neq Y_i$, let $j$ be the smallest such $i$. If $X_j < Y_j$, then $X < Y$; if $X_j > Y_j$, then $X > Y$.
Constraints
- All input values are integers.
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq N$
- $1 \leq A_i \leq N$
Input
The input is given from standard input in the following format.
$N$ $K$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$
Output
If the sequence $B$ is the answer, print the elements of $B$ separated by spaces.
$B_{1}$ $B_{2}$ $\dots$ $B_{N-1}$
Sample
Sample 1
Input
3 3 2 1 1
Output
2 1
We have $X_1 = (1,1), X_2 = (2,1), X_3 = (2,1)$. Sorting these in ascending lexicographic order gives $(1, 1), (2, 1), (2, 1)$. Therefore, $(2,1)$ is the $3$-rd smallest in lexicographic order.
Sample 2
Input
5 3 3 1 4 1 5
Output
3 1 4 1
We have $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)$. Sorting these in ascending lexicographic order gives $(1,4,1,5), (3,1,1,5), (3,1,4,1), (3,1,4,5),(3,4,1,5)$. The $3$-rd in lexicographic order is $(3, 1, 4, 1)$.
Sample 3
Input
10 8 3 6 8 1 10 5 7 2 4 9
Output
3 6 8 10 5 7 2 4 9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。