You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目还是简单一点好。

给定自然数 $n$、$k$、$x$，你要求出第 $k$ 小的长度为 $n$ 的逆序对对数为 $x$ 的 $1\sim n$ 的排列 $a_1,a_2 ... a_n$ ，然后用仙人图上在线分支定界启发式带花树上下界最小费用流解决问题，保证存在。

注：逆序对为满足 $i<j$、$a_i>a_j$ 的 $(i,j)$。比较为字典序比较，即比较从前往后第一个不同的位置。第 $k$ 小从 $1$ 开始标号。一个 $1\sim n$ 的排列定义为一个长度为 $n$ 的数列，排序完可以得到 $1\sim n$。

输入格式

一行三个自然数 $n$、$k$、$x$。

输出格式

输出满足条件的排列，一行n个数，用空格分隔。

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

提示

对于 $10\%$ 的数据，$n \leq 8$。

对于 $30\%$ 的数据，$n \leq 10$。

对于 $50\%$ 的数据，$n \leq 50$。

对于另外 $20\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$1 \leq n \leq 300$，$1 \leq k \leq 10^{13}$，保证存在符合题意的排列。