Logo Infinity Online Judge

InfOJ

时间限制:4 s 空间限制:512 MB

#97. 排列

统计

题目描述

给出 $1\sim n$ 的排列 $p$,下标从 $1$ 开始。

恰好 $k$ 次任意选择 $1\le i\le n-1$ 并交换 $p_i,p_{i+1}$。问交换完毕后,字典序最小的排列 $p$ 是什么?

输入格式

第一行两个非负整数 $n,K$,分别表示排列中数的个数和交换次数。

接下来一行 $n$ 个整数,描述排列 $p$。

输出格式

一行以空格隔开的 $n$ 个正整数,描述交换完成之后的排列。

样例

样例输入 1

5 2
2 1 4 3 5

样例输出 1

1 2 3 4 5

样例输入 2

5 3
5 4 3 2 1

样例输出 2

2 5 4 3 1

样例输入 3

5 6
5 4 3 2 1

样例输出 3

1 3 5 4 2

数据范围与提示

本题捆绑测试。

对于所有数据,$2\le n\le 5\times 10^5$,$0\le K\le 10^{12}$。保证操作合法。

详细数据范围如下表:

Subtask 编号 $n$ $K$ 分数
$1$ $\le 8$   $30$
$2$ $\le 10^3$   $30$
$3$ $\le 10^3$ $=10^{12}$ $15$
$4$ $\le 5\times 10^5$   $25$