DMOPC '21 Contest 8 P3 - Weaker Data

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Two days before the contest, Keenan proposed the following lovely problem as the third problem of the DMOPC:

Given a permutation P of the first N positive integers, a valley is a triplet of indices 1 \le i < j < k \le N such that P_i > P_j < P_k. Count the number of valleys.

Unfortunately, it has neither flavourtext nor data. Now that Edward has finished with the flavourtext, it is your job to generate the data. Specifically, Keenan wants a case with a permutation of length N where the answer is K. Of course, it is also known that he has a peculiar obsession with lexicographically small permutations. Thus, you are to generate the lexicographically smallest permutation satisfying his desires, or determine that no such permutation exists.

Constraints

1 \le N \le 10^6

0 \le K \le 10^{18}

Subtask 1 [20%]

1 \le N \le 30

Subtask 2 [40%]

1 \le N \le 5 \times 10^3

Subtask 3 [40%]

No additional constraints.

Input Specification

The first and only line of input contains 2 space-separated integers N and K.

Output Specification

On a single line, output the lexicographically smallest permutation of the first N integers with K valleys, or -1 if none exist.

Scoring

You will receive 50% of the marks for a case if your permutation of length N generates the desired output of K but is not lexicographically minimum.

Sample Input 1

5 4

Sample Output 1

2 1 4 3 5

Explanation for Sample 1

The valleys are (1, 2, 3), (1, 2, 4), (1, 2, 5), and (3, 4, 5). It can be proven that this arrangement is lexicographically minimum.

Sample Input 2

4 100

Sample Output 2

-1

Sample Input 3

10 20

Sample Output 3

1 2 3 7 9 5 4 6 8 10

Comments

There are no comments at the moment.