SPOJ.com - Problem SHP

SHP - Shuffling Problem

#adhoc

You are given an unordered array with n distinct numbers from 1 to n. You have to perform exactly k swaps and print the lexicographically largest array that can be obtained.

In one swap, you can choose any two distinct indices and swap the elements at those indices.

Input

First line consists of 2 integers n (1 < n ≤ 100000) and k (0 ≤ k ≤ 10⁹).

Next line consists of n integers (a₀, a₁ ... a_n-1).

Output

You have to print lexicographically largest array obtained.

Example

Input:
5 2
1 2 4 3 5

Output:
5 4 2 3 1

Submit solution!

hide comments



	Amitayush Thakur: 2021-02-19 19:01:14 What is the meaning of "lexicographically largest array" ? If n = 12, then is 12 11 10 9 8 7 6 5 4 3 2 1 the largest or 9 8 7 6 5 4 3 2 12 11 10 1 is the largest or something else ? I could clearly find no standard definition online about this. Also, what is the meaning of "distinct indices" ? Does mean if two indices are swapped, then they cannot be swapped again ? However, I think if k > nn, which is quite possible, the same pair indices are bound to repeat. I have a feeling that problem lacks proper definitions, explainations and examples which would help the solver even understand the problem statement completely. [NG]: https://en.wikipedia.org/wiki/Lexicographical_order . Swapping elements at distinct indexes allowed = swapping element with itself not allowed. Statement is simple and concise and the problem was understood and solved by multiple users even before suhash and sgtlaugh kinda nitpicked on it, getting psetter to get rid of any inaccuracies. Have you even tried your solution against a bruteforce? [Amitayush] Thanks NG for your help :) . I had read the wiki page earlier as well. My question was more in context of considering the numbers as strings and then sorting them in dictionary order (i.e. 1 < 10 < 100 < 11 < ... < 2 < 20 < ... ). I finally realized that for this problem the largest is simply the array sorted in descending order, I was overthinking that a bit. Also, the same indices can be swapped again and again, for example A[i] can be swapped with A[j] as many times as one wants, as long as i != j. Finally, I was able to get AC keeping these things in mind. Last edit: 2021-02-20 07:24:53*
	Amitayush Thakur: 2021-02-13 21:28:15 Is it allowed to swap the same pair of indices again and again. For example, for the test case: 12 14 1 2 3 4 5 6 7 8 9 10 11 12 Is the answer this: 9 8 7 6 5 4 3 2 12 11 10 1 ?? PS: I realised that for sufficiently large k (when > nn) this is anyway bound to happen Last edit: 2021-02-14 05:45:43*
	vineetjai: 2020-09-10 15:31:30 Awesome problem.
	kprock41951: 2020-07-15 16:42:38 ah! frustrating!! Last edit: 2020-07-15 19:37:34
	offamitkumar: 2020-06-23 05:55:09 Keep in mind [spoilers removed]. Cost me 5 WA. [NG]: Getting it right is the main challenge here. You've done it, let others enjoy that satisfaction as well. Solver: Guys surprise is waiting for you, MUST TRY PROBLEM. Last edit: 2020-06-23 06:51:32
	Scape: 2020-06-21 22:30:20 @robosapien, can you give me a case for which my submission fails? Can't figure it out. Am I misunderstanding the problem? Can we swap an index with itself? [Edit]: You should mention we are not allowed to swap an index with itself, i.e they need to be distinct. Last edit: 2020-06-21 23:33:59
	robosapien: 2020-06-21 14:29:31 Thanks. Fixed.
	suhash: 2020-06-21 07:59:41 There are cases with n = 1 and k > 0 (which are invalid). Please fix them in the input.
	nadstratosfer: 2020-06-19 04:13:18 Please don't set TL below 1s in Classical, it might prevent AC with an efficient solution in a language with interpreter/VM startup lag (albeit in case of this problem Python does pass).

Submit solution!

Added by:	robosapien
Date:	2020-06-18
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All