102625: [AtCoder]ABC262 F - Erase and Rotate

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 1

5 3
4 5 2 3 1

Sample Output 1

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 2

3 0
3 2 1

Sample Output 2

3 2 1

You may be unable to perform operations.


Sample Input 3

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

Sample Output 3

1 3 4 7 2 8 11 9

Input

题意翻译

给定一个排列 $\{a_n\}$,有两种操作: - 将最后数提到最前(Rotate) - 删除一个数(Erase) 求操作不超过 $k$ 次后最小字典序。 第一行输入 $n,k$,第二行输入 $\{a_n\}$。输出一行数,代表最小字典序。

Output

得分:500分

问题描述

给你一个序列 $P = (p_1,p_2,\ldots,p_N)$,其中恰好包含$1,2,\ldots,N$各一次。
你可以按任意顺序进行0到$K$次以下操作:

  • 选择$P$中的一个项并删除它。
  • 将$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$各一次。
  • 输入中的所有值都是整数。

输入

从标准输入获取以下格式的输入:

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

输出

用空格分隔,打印通过操作可以得到的字典序最小的$P$。


样例输入1

5 3
4 5 2 3 1

样例输出1

1 2 3

以下操作使$P$等于$(1,2,3)$。

  • 删除第一个项使$P$等于$(5,2,3,1)$。
  • 将最后一个项移动到头部使$P$等于$(1,5,2,3)$。
  • 删除第二个项使$P$等于$(1,2,3)$。

无法使$P$字典序小于$(1,2,3)$,所以这是答案。


样例输入2

3 0
3 2 1

样例输出2

3 2 1

你可能无法进行操作。


样例输入3

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

样例输出3

1 3 4 7 2 8 11 9

加入题单

上一题 下一题 算法标签: