Largest Permutation

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

There are no comments at the moment.