小清新签到题

题目描述

题目还是简单一点好。 给定自然数 $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个数,用空格分隔。

输入输出样例

输入样例 #1

3 2 2

输出样例 #1

3 1 2

输入样例 #2

10 6 4

输出样例 #2

1 2 3 4 5 7 6 10 9 8

输入样例 #3

50 233 233

输出样例 #3

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

输入样例 #4

50 233333333 333

输出样例 #4

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}$,保证存在符合题意的排列。