Inversion Count

5

1 votes
Ad-Hoc, Medium
Problem

Given N and K, output the permutation of numbers from 1 to N such that the inversion count of the resultant sequence is K and it is lexicographically smallest possible.

Inversion count: For an array A, number of ordered pairs (i, j) such that Ai > Aj and i < j.

If no permutation with inversion count K is possible, output -1.

Input:

Single line containing N and K separated by a space.

Output:

Required permutation if it exist, else -1.

Constraints:​​​​​​​

  • 1 ≤ N ≤ 3*106
  • 0 ≤ K ≤ 1014
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?