F - Erase and Rotate

Contest Duration: 2022-07-31(Sun) 12:00 - 2022-07-31(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Erase and Rotate Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$1,2,\ldots,N$ がちょうど $1$ 回ずつ現れる数列 $P = (p_1,p_2,\ldots,p_N)$ が与えられます。
あなたは以下の操作のうち $1$ つを選んで行うことを $0$ 回以上 $K$ 回以下繰り返せます。

$P$ の項を $1$ つ選び、削除する。
$P$ の末尾の項を先頭に移動させる。

操作後の $P$ として考えられるもののうち辞書順で最小のものを求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq K \leq N-1$
$1 \leq p_i \leq N$
$(p_1,p_2,\ldots,p_N)$ には $1,2,\ldots,N$ がちょうど $1$ 回ずつ現れる。
入力はすべて整数

入力

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

 $N$   $K$ 
 $p_1$   $p_2$   $\ldots$   $p_N$

出力

操作後の $P$ として考えられるもののうち辞書順で最小のものを空白区切りで出力せよ。

入力例 1Copy

Copy

5 3
4 5 2 3 1

出力例 1Copy

Copy

1 2 3

以下のように操作をすると $P$ は $(1,2,3)$ になります。

先頭の項を削除する。これによって $P$ は $(5,2,3,1)$ になる。
末尾の項を先頭に移動させる。これによって $P$ は $(1,5,2,3)$ になる。
先頭から $2$ 番目の項を削除する。これによって $P$ は $(1,2,3)$ になる。

また、辞書順で $(1,2,3)$ より小さい数列は操作後の $P$ として考えられません。よってこれが答えです。

入力例 2Copy

Copy

3 0
3 2 1

出力例 2Copy

Copy

3 2 1

操作を $1$ 回も行えない場合があります。

入力例 3Copy

Copy

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

出力例 3Copy

Copy

1 3 4 7 2 8 11 9

Score : $500$ points

Problem Statement

You are given a sequence $P = (p_1,p_2,\ldots,p_N)$ that contains $1,2,\ldots,N$ exactly once each.
You may perform the following operations between $0$ and $K$ times in total in any order:

Choose one term of $P$ and remove it.
Move the last term of $P$ to the head.

Find the lexicographically smallest $P$ that can be obtained as a result of the operations.

Constraints

$1 \leq N \leq 2 \times 10^5$
$0 \leq K \leq N-1$
$1 \leq p_i \leq N$
$(p_1,p_2,\ldots,p_N)$ contains $1,2,\ldots,N$ exactly once each.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$ 
 $p_1$   $p_2$   $\ldots$   $p_N$

Output

Print the lexicographically smallest $P$ that can be obtained as a result of the operations, separated by spaces.

Sample Input 1Copy

Copy

5 3
4 5 2 3 1

Sample Output 1Copy

Copy

1 2 3

The following operations make $P$ equal $(1,2,3)$ .

Removing the first term makes $P$ equal $(5,2,3,1)$ .
Moving the last term to the head makes $P$ equal $(1,5,2,3)$ .
Removing the second term makes $P$ equal $(1,2,3)$ .

There is no way to obtain $P$ lexicographically smaller than $(1,2,3)$ , so this is the answer.

Sample Input 2Copy

Copy

3 0
3 2 1

Sample Output 2Copy

Copy

3 2 1

You may be unable to perform operations.

Sample Input 3Copy

Copy

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

Sample Output 3Copy

Copy

1 3 4 7 2 8 11 9