COCI '17 Contest 5 #4 Karte

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

… Take these cards, I tell ya, my cousin from Sweden sent them when the hunger for war was at its peak, and we stayed playing rummy in the trenches.

Daniel: "Are we playin' rummy, eh?"

Domagoj: "Well ok then."

Daniel: "Watch this now. You have a deck of N cards, where the i^\text{th} card has a claim written on it in the form of 'At least a_i cards beneath this one contain a false claim.' You have to shuffle them so that exactly K cards contain a false claim."

Domagoj: "You destroy me in this game every time, where did you get these cards, son?!"

Daniel: "Ah, my old man organizes card tournaments, so each day he gives me free cards, ten bucks per deck."

Your task is to help Domagoj solve Daniel's task. Output the order in which Domagoj must place the cards. It is also possible that this is a bad joke on Daniel's part, and that there is no possible order to place the cards in. In that case, output -1.

Input Specification

The first line contains integers N and K (1 \leq N \leq 5 \times 10^5, 0 \leq K \leq N).

The i^\text{th} of the following N lines contains an integer a_i (0 \leq a_i \leq 5 \times 10^5).

Output Specification

If the required order does not exist, output -1.

Otherwise, in a single line, output N integers separated by spaces, the numbers on the cards in the order from the top to the bottom of the deck. If there are multiple solutions, output any.

Scoring

In test cases worth 30\% of total points, it will hold N \leq 16.

In additional test cases worth 40\% of total points, it will hold N \leq 2\,000.

Sample Input 1

4 2
1
2
2
3

Sample Output 1

2 3 1 2

Sample Input 2

5 3
2
1
3
0
3

Sample Output 2

3 3 0 1 2

Explanation for Sample Output 2

For simplicity's sake, we'll label the cards as true/false, depending on the claims written on them.

Beneath the fifth card there are 0 false cards, so it is false.

Beneath the fourth card there is 1 false card, so it is true.

Beneath the third card there is 1 false card, so it is true.

Beneath the second card there is 1 false card, so it is false.

Beneath the first card there are 2 false cards, so it is false.

Therefore, we have a total of 3 false cards.

Sample Input 3

6 4
0
2
5
2
0
1

Sample Output 3

-1

Comments

There are no comments at the moment.