Turning Permutation
题目描述
长度为 n 的排列是一个由 n 个整数组成的序列,其中 1 到 n 每个整数恰好出现一次。
对于排列 p1,p2,…,pn,令 qi 表示整数 i 在排列中出现的位置,即 pqi=i。如果对于每个 i=2,3,…,n−1,都有
(qi−qi−1)(qi−qi+1)>0,
则称 p 为一个 turning permutation(转折排列)。约束作用于逆排列 q,要求每个内部位置都是严格局部极大值或严格局部极小值。
给定 n 和 k,求所有长度为 n 的转折排列按字典序从小到大排序后的第 k 个。如果这样的排列不足 k 个,报告不存在。
比较两个不同的长度为 n 的排列 x,y 时,找到它们第一个不同的位置 i;当且仅当 xi<yi 时,x 的字典序更小。
输入格式
唯一一行包含两个整数 n,k,其中 3≤n≤50,1≤k≤1018。它们分别表示排列长度和所求排列在字典序升序列表中的排名。排名从 1 开始,没有外层测试组数。
输出格式
若长度为 n 的转折排列不足 k 个,输出一行 -1。
否则,输出一行 n 个整数,表示字典序第 k 小的转折排列 p。
原样例 1
3 2
2 1 3
原样例 2
3 5
-1
原样例 3
4 6
3 1 2 4
原样例 4
4 11
-1
原样例说明
长度为 3 的转折排列共 4 个,按字典序升序依次是:
[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]。
因此样例 1 的第 2 小排列是 [2,1,3],样例 2 不存在答案。
长度为 4 的转折排列共 10 个,按字典序升序依次是:
[1,3,2,4]、[1,3,4,2]、[2,1,4,3]、[2,4,1,3]、[2,4,3,1]、[3,1,2,4]、[3,1,4,2]、[3,4,1,2]、[4,2,1,3]、[4,2,3,1]。
因此样例 3 的第 6 小排列是 [3,1,2,4],样例 4 不存在答案。