#P3580. 冒泡排序

冒泡排序

题目描述

下面是一段实现冒泡排序算法的 C++ 代码:

for(int i=1;i<n;i++)
for(int j=1;j<=n-i;j++)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);

其中待排序的 aa 数组是一个 1−n1-n 的排列,swap 函数将交换数组中对应位置的值。

对于给定的数组 aa 以及给定的非负整数 kk,使用这段代码执行了正好 kk 次 swap 操作之后数组 aa 中元素的值会是什么样的呢?

输入格式

输入文件共两行。
第一行包含空格隔开的一个正整数 nn 和一个非负整数 kk。
第二行包含 nn 个空格隔开的互不相同的正整数,表示初始时 aa 数组中的排列。

输出格式

输出文件共一行。
若在执行完整个代码之后执行 swap 的次数仍不够 kk,那么输出一个字符串 Impossible! (不含引号),否则按顺序输出执行 swap 操作 kk 次之后数组 aa 的每一个元素,用空格隔开。

1 1
1
Impossible!

数据规模与约定

对于 100%100\% 的数据满足 n≤106n\le 10^6,k≤1012k\le 10^{12}。

题目来源

By 佚名提供