DMOPC '18 Contest 1 P4 - Sorting

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Java 5.0s
Python 5.0s
Memory limit: 256M

Author:
Problem types

You have a sorted list of numbers in increasing order from to . This list has elements. Some numbers may appear multiple times, so you have recorded the number of occurrences of each number in this list, . However, you messed up when assigning the indices, so is actually the number of occurrences of , for some unknown permutation of . You recall that for some and . Find a permutation that satisfies this. If no such permutation exists, output -1.

You will be rewarded even if you can only determine the existence of such a . Outputting any permutation of if there exists a permutation and -1 otherwise for every test case of a subtask will earn you half of the subtask's points, assuming you do not already receive the full points (if one of the permutations outputted is wrong, but there does exist a permutation).

Constraints         Input Specification

The first line will contain three space-separated integers , , , and .
The next line will contain space-separated integers .

Output Specification

If there exists a permutation, output space-separated integers . There may be many valid permutations. Any one of them will be accepted.
If there does not exist a permutation, output -1.

3 10 5 1
4 5 1

2 1 3

Explanation for Sample 1

There are six possible lists :

1 1 1 1 2 2 2 2 2 3
1 1 1 1 2 3 3 3 3 3
1 1 1 1 1 2 2 2 2 3
1 1 1 1 1 2 3 3 3 3
1 2 2 2 2 3 3 3 3 3
1 2 2 2 2 2 3 3 3 3

The third list satisfies . The corresponding which gives this list is .

6 9 4 4
2 2 2 1 1 1

4 5 6 1 2 3

6 9 3 4
2 2 2 1 1 1

-1