Description

Let's keep the problem simple.

Given natural numbers $n$, $k$, $x$, you are required to find the $k$-th smallest permutation $a_1,a_2 ... a_n$ of $1\sim n$ of length $n$ whose number of inversions is $x$ and then solve the problem using an on-cactus online branch-and-bound heuristic blossom-tree min-cost flow with bounds, and it is guaranteed to exist.

Note: An inversion is a pair $(i,j)$ such that $i<j$ and $a_i>a_j$. The comparison is lexicographical, i.e., compare from left to right at the first position where they differ. The $k$-th smallest is 1-indexed. A permutation of $1\sim n$ is defined as a length-$n$ sequence that, after sorting, becomes $1\sim n$.

Input Format

One line with three natural numbers $n$, $k$, $x$.

Output Format

Output a permutation that satisfies the conditions: one line with $n$ numbers, separated by spaces.

3 2 2

3 1 2

10 6 4

1 2 3 4 5 7 6 10 9 8

50 233 233

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 32 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 33 35 34 31 30 29 28

50 233333333 333

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 43 49 50 47 46 45 48 44 41 42 40 39 37 38 36 35 34 33 32 30 29 31 28 25 26 27 24

Hint

For $10\%$ of the testdata, $n \leq 8$.

For $30\%$ of the testdata, $n \leq 10$.

For $50\%$ of the testdata, $n \leq 50$.

For an additional $20\%$ of the testdata, $k=1$.

For $100\%$ of the testdata, $1 \leq n \leq 300$, $1 \leq k \leq 10^{13}$, and a valid permutation is guaranteed to exist.

Translated by ChatGPT 5