F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:今天的月赛题在https://begin.lydsy.com/JudgeOnline/upload/201805.pdf
Problem 5170. -- Fable

5170: Fable

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 46  Solved: 23
[Submit][Status][Discuss]

Description

有这么一则传闻,O(nlogn)的排序发明之前,滋滋国的排序都是采用的冒泡排序。即使是冒泡排序,对当时的国民
来说也太复杂太难以理解,于是滋滋国出现了这样一个职业——排序使,收取报酬并负责给序列排序。作为冒泡协
会首席排序使,Lyra收费颇高,为了照顾并不富裕的人,Lyra允许顾客只支付一部分酬劳并获得并不完美的冒泡排
序服务。众所周知,n个元素的冒泡排序需要n?1n-1轮才能完成,有一位顾客支付的费用,只能够完成前k轮的排序
。作为冒泡排序的首席排序使,天赋卓绝的Lyra暗地里早就掌握了O(nlogn)的排序方法,这也是她轻松当选首席排
序使的原因——排序速度无人能敌。而现在面对只能够完成前k轮冒泡排序的要求,Lyra犯了难,于是她来寻求你
的帮助。给定一个序列,执行如下程序:
for i from 1 to k
    for j from 1 to n-1
         if Aj>Aj+1
            swap(Aj,Aj+1)
并输出之后的A序列。

Input

第一行两个整数n,k表示序列的长度和轮数。
接下来n行每行一个整数表示Ai
1≤k<n≤200000;1≤Ai≤10^9

Output

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

Sample Input

3 1
3
2
1

Sample Output

2
1
3

HINT

Source

By C_SUNSHINE

[Submit][Status][Discuss]

HOME Back