#P18460. Turning Permutation

Turning Permutation

Turning Permutation

题目描述

长度为 nn 的排列是一个由 nn 个整数组成的序列,其中 11 到 nn 每个整数恰好出现一次。

对于排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,令 qiq_i 表示整数 ii 在排列中出现的位置,即 pqi=ip_{q_i}=i。如果对于每个 i=2,3,…,n−1i=2,3,\ldots,n-1,都有

(qi−qi−1)(qi−qi+1)>0,(q_i-q_{i-1})(q_i-q_{i+1})>0,

则称 pp 为一个 turning permutation(转折排列)。约束作用于逆排列 qq,要求每个内部位置都是严格局部极大值或严格局部极小值。

给定 nn 和 kk,求所有长度为 nn 的转折排列按字典序从小到大排序后的第 kk 个。如果这样的排列不足 kk 个,报告不存在。

比较两个不同的长度为 nn 的排列 x,yx,y 时,找到它们第一个不同的位置 ii;当且仅当 xi<yix_i<y_i 时,xx 的字典序更小。

输入格式

唯一一行包含两个整数 n,kn,k,其中 3≤n≤503\le n\le50,1≤k≤10181\le k\le10^{18}。它们分别表示排列长度和所求排列在字典序升序列表中的排名。排名从 11 开始,没有外层测试组数。

输出格式

若长度为 nn 的转折排列不足 kk 个,输出一行 -1。

否则,输出一行 nn 个整数,表示字典序第 kk 小的转折排列 pp。

原样例 1

3 2
2 1 3

原样例 2

3 5
-1

原样例 3

4 6
3 1 2 4

原样例 4

4 11
-1

原样例说明

长度为 33 的转折排列共 44 个,按字典序升序依次是:

[1,3,2][1,3,2]、[2,1,3][2,1,3]、[2,3,1][2,3,1]、[3,1,2][3,1,2]。

因此样例 1 的第 22 小排列是 [2,1,3][2,1,3],样例 2 不存在答案。

长度为 44 的转折排列共 1010 个,按字典序升序依次是:

[1,3,2,4][1,3,2,4]、[1,3,4,2][1,3,4,2]、[2,1,4,3][2,1,4,3]、[2,4,1,3][2,4,1,3]、[2,4,3,1][2,4,3,1]、[3,1,2,4][3,1,2,4]、[3,1,4,2][3,1,4,2]、[3,4,1,2][3,4,1,2]、[4,2,1,3][4,2,1,3]、[4,2,3,1][4,2,3,1]。

因此样例 3 的第 66 小排列是 [3,1,2,4][3,1,2,4],样例 4 不存在答案。