题面（vjudge）｜题解：

这些排列组合的产生过程如下。我们将按照从 $1$ 到 $n$ 的顺序贪婪地浏览这些数字，并将每个数字放在第一个空格或最后一个空格中。例如，如果我们想把 $4$ 放进排列组合 $1, 3, \circ, \circ, \dots, \circ, 2$ 中，我们可以把它放在第三个空格中，也可以放在最后面的第二个空格中。也就是说，排列先增加后减少。

我们可以证明贪心算法就是这样运行的。现在，让我们输入数字 $i$ 。当我们放上这个数字时，我们可以立即知道，其中一个末端是所选位置的线段上的最小值等于 $i$ （我们不考虑已经放上的小于 $i$ 的数字）。这些线段的数目等于 $n - i + 1$ 。我们得到的答案等于这个固定数字与我们未来得到的数字之和。假设我们没有将数字 $i$ 放在数组的末尾。让我们进一步考虑最佳答案： $[\dots, x_j, \dots] i [\dots, x_j, \dots]$ .现在我们把 $i$ 放在数组的末尾，并保持下面元素的顺序不变。所有末端位于大于 $i$ 的元素上的线段可能不再覆盖数字 $i$ ，但它们所覆盖的大于 $i$ 的数字集合没有改变。所以答案变得更好了。

由于我们独立地选择其中一端，因此有 $2^{n - 1}$ 种这样的排列，我们可以用一个简单的循环找到 $k$ -th一种排列，类似于把一个数字转换成二进制符号。

std：

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;
        cin >> n >> k;
        vector <int> a, b;
        
        if (n <= 60 && (1ll << (n - 1)) < k) {
            cout << -1 << endl;
            continue;
        }
        k--;
        vector <int> d;
        while (k) {
            d.push_back(k % 2);
            k /= 2;
        }
        while (d.size() < n - 1) d.push_back(0);
        
        for (int i = n - 2, j = 1; i >= 0; i--, j++) {
            if (d[i] == 0) a.push_back(j);
            else b.push_back(j);
        }
        
        reverse(b.begin(), b.end());
        for (int i : a) cout << i << ' ';
        cout << n << ' ';
        for (int i : b) cout << i << ' ';
        cout << endl;
    }
 
    return 0;
}

求助 std 里“简单的循环”的工作原理，蒟蒻看了 1h 都没看懂 /kel