P3672 A Simple Sign-in Problem

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 $ia_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$.

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

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

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