#6130. 「2017 山东三轮集训 Day1」Fable

内存限制:233 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有这么一则传闻, O(n \log n) 的排序发明之前,滋滋国的排序都是采用的冒泡排序。即使是冒泡排序,对当时的国民来说也太复杂太难以理解,于是滋滋国出现了这样一个职业 —— 排序使,收取报酬并负责给序列排序。

作为冒泡协会首席排序使,Lyra 收费颇高,为了照顾并不富裕的人,Lyra 允许顾客只支付一部分酬劳并获得并不完美的冒泡排序服务。众所周知, n 个元素的冒泡排序需要 n - 1 轮才能完成,有一位顾客支付的费用,只能够完成前 k 轮的排序。

作为冒泡排序的首席排序使,天赋卓绝的 Lyra 暗地里早就掌握了 O(n \log n) 的排序方法,这也是她轻松当选首席排序使的原因 —— 排序速度无人能敌。而现在面对只能够完成前 k 轮冒泡排序的要求,Lyra 犯了难,于是她来寻求你的帮助。

给定一个序列,执行如下程序:

\begin{aligned} & \textbf{for} \ i \ \textbf{from} \ 1 \ \textbf{to} \ k \\ & \hskip{2 em} \textbf{for} \ j \ \textbf{from} \ 1 \ \textbf{to} \ n - 1 \\ & \hskip{4 em} \textbf{if} \ A_j > A_{j + 1} \\ & \hskip{6 em} \textbf{swap}(A_j, A_{j + 1}) \end{aligned}

并输出之后的 A 序列。

输入格式

第一行两个整数 n, k ,表示序列的长度和轮数。
接下来 n 行每行一个整数表示 A_i

输出格式

输出 n 行每行一个整数表示冒泡排序 k 轮后的 A_i

样例

样例输入 1

3 1
3
2
1

样例输出 1

2
1
3

样例输入 2

见「附加文件」中的 ex_fable2.in

样例输出 2

见「附加文件」中的 ex_fable2.out

数据范围与提示

对于全部数据, 1 \leq k < n \leq 200000; 1 \leq A_i \leq 10 ^ 9

子任务 1(3 分) n \leq 2000
子任务 2(29 分) n \leq 100000 ,所有的 A_i 均为随机生成;
子任务 3(68 分) n \leq 200000