Largest Permutation

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

You are given an array of N integers which is a permutation of the first N natural numbers. You can swap any two elements of the array. You can make at most K swaps. What is the largest permutation, in numerical order, you can make?

Input Specification

The first line of the input contains two integers, N and K, the size of the input array and the maximum swaps you can make, respectively. The second line of the input contains a permutation of the first N natural numbers.

Output Specification

Print the lexicographically largest permutation you can make with at most K swaps.

Constraints

1 \le N \le 10^5
1 \le K \le 10^9

Sample Input 1

5 1
4 2 3 5 1

Sample Output 1

5 2 3 4 1

Explanation of Output for Sample Input 1

You can swap any two numbers in [4,2,3,5,1] and see the largest permutation is [5,2,3,4,1].

Sample Input 2

3 1
2 1 3

Sample Output 2

3 1 2

Explanation of Output for Sample Input 2

With 1 swap we can get [1,2,3], [3,1,2] and [2,3,1], out of these [3,1,2] is the largest permutation.

Sample Input 3

2 1
2 1

Sample Output 3

2 1

Explanation of Output for Sample Input 3

We can see that [2,1] is already the largest permutation. So we don't need any swaps.

Original Problem Author: MeHdi_KaZemI8; Problem Resource: HackerRank


Comments


  • 1
    Xiang_li  commented on Aug. 21, 2021, 6:26 p.m.

    I don't think this is worth 10 points