← 返回题目列表

Codeforces · 2040/C

C. 有序排列

中文机器翻译题面 查看原题

考虑从 $$$1$$$ 到 $$$n$$$ 的整数的排列$$$^{\text{*}}$$$ $$$p_1, p_2, \ldots, p_n$$$。我们可以为其引入以下总和$$$^{\text{†}}$$$:

$$$$$$S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l + 1}, \ldots, p_r)$$$$$$

让我们考虑长度为 $$$n$$$ 且最大可能值为 $$$S(p)$$$ 的所有排列。按字典顺序输出$$$k$$$^{\text{‡}}$$$顺序,或者报告它们的数量少于$$$k$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) - 排列的长度和所需排列的索引号。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。

输出

对于每个测试用例,如果合适的排列少于$$$k$$$,则打印$$$-1$$$。

否则,打印第 $$$k$$$ 个合适的排列。

示例

输入 #1

6
3 2
3 3
4 11
4 6
6 39
7 34

输出 #1

1 3 2 
2 3 1 
-1
2 4 3 1 
-1
2 3 4 5 7 6 1

注意

让我们计算长度为 $$$3$$$ 的所有排列所需的总和(按字典顺序排序):

$$$S(p)$$$$$$的排列值[1, 2, 3]$$$$$$10$$$$$$[1, 3, 2]$$$$$$10$$$$$$[2, 1, 3]$$$$$$9$$$$$$[2, 3, 1]$$$$$$10$$$$$$[3, 1, 2]$$$$$$9$$$$$$[3, 2, 1]$$$$$$10$$$

在第一个测试用例中,您必须打印长度 $$$3$$$ 的第二个合适的排列。查看表格,我们看到它是排列 $$$[1, 3, 2]$$$。

在第二个测试用例中,您必须打印长度为 $$$3$$$ 的第三个合适的排列。查看表格,我们看到它是排列 $$$[2, 3, 1]$$$。