DMOPC '18 Contest 1 P4 - Sorting

View as PDF

Submit solution



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

Problem types

You have a sorted list A of numbers in increasing order from 1 to N. This list has M elements. Some numbers may appear multiple times, so you have recorded the number of occurrences of each number in this list, f_1, f_2, \ldots, f_N. However, you messed up when assigning the indices, so f_i is actually the number of occurrences of P_i, for some unknown permutation P of 1, 2, \ldots, N. You recall that A_K=X for some K and X. Find a permutation P that satisfies this. If no such permutation P exists, output -1.

You will be rewarded even if you can only determine the existence of such a P. Outputting any permutation of 1, 2, \ldots, N 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

1\le X\le N
1\le K\le M\le 2\cdot 10^{11}
1\le f_i \le 1\ 000\ 000
f_1+f_2+\ldots +f_N = M

Subtask 1 [10%]

1\le N\le 8

Subtask 2 [20%]

1\le N\le 20

Subtask 3 [20%]

1\le N\le 400

Subtask 4 [10%]

1\le N\le 2\ 000

Subtask 5 [40%]

1\le N\le 200\ 000

Input Specification

The first line will contain three space-separated integers N, M, K, and X.
The next line will contain N space-separated integers f_1, f_2, \ldots, f_N.

Output Specification

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

Sample Input 1

3 10 5 1
4 5 1

Sample Output 1

2 1 3

Explanation for Sample 1

There are six possible lists A:

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 A_K=X. The corresponding P which gives this list is 2,\ 1,\ 3.

Sample Input 2

6 9 4 4
2 2 2 1 1 1

Sample Output 2

4 5 6 1 2 3

Sample Input 3

6 9 3 4
2 2 2 1 1 1

Sample Input 3

-1

Comments

There are no comments at the moment.