Almost Sorted

发表于 分类于 ，

    如果一个长度为 $n$ 的排列 $a$ 满足对于任意整数 $i\in[1,n-1]$ 都有 $a_{i+1}\geq a_i-1$，我们就说这个排列是“几乎有序的”。

    给定 $n,k$，求所有长度为 $n$ 的“几乎有序的”排列中，字典序第 $k$ 小的那个。特别的，如果这样的排列不存在，输出 $-1$。$T$ 组数据。

    $1\leq T\leq10^3;1\leq n,\sum n\leq10^5;1\leq k\leq10^{18};$

Almost Sorted

Created by LXC on Thu Apr 11 23:54:21 2024

https://codeforces.com/problemset/problem/1508/B

ranting: 1800

tag: binary search, combinatorics, constructive algorithms, implementation

problem

如果一个长度为 $n$ 的排列 $a$ 满足对于任意整数 $i\in[1,n-1]$ 都有 $a_{i+1}\geq a_i-1$，我们就说这个排列是“几乎有序的”。

给定 $n,k$，求所有长度为 $n$ 的“几乎有序的”排列中，字典序第 $k$ 小的那个。特别的，如果这样的排列不存在，输出 $-1$。$T$ 组数据。

$1\leq T\leq10^3;1\leq n,\sum n\leq10^5;1\leq k\leq10^{18};$

solution

打表发现规律，改变从倒数第i个数开始后缀的数。有$2^i$能得到个不同的数。

于是最多只需要考虑后面60个数的位置交换。实际上是对k进行二进制分解。手动模拟一下就知道了。

code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    // auto check = [&]() {
    //     for (int i=1; i<n; i++) {
    //         if (a[i] < a[i-1]-1) {
    //             return false;
    //         }
    //     }
    //     return true;
    // };
    // int cnt = 0;
    // do {
    //     if (check()) {
    //         cout << a << " ";
    //         cout << (cnt++);
    //         cout << endl;
    //     }
    // }
    // while (next_permutation(a.begin(), a.end()));
    k--;
    int p = 60;
    while (k>0 && p != -1) {
        // cout << k << endl;
        while (p>0 && k<=(1LL<<p-1)-1) p--; // 最后一个大于等于k的位置
        ll s = (1LL<<p)-1;
        int l = n-1-p;
        if (l<0) break;
        while (p>0 && s-(1LL<<p-1)+1 <= k) p--; // 最后一个差值小于等于k的位置
        k -= s-(1LL<<p)+1;
        int r = n-p;
        // cout << l << " " << r << endl;
        reverse(a.begin()+l, a.begin()+r);
        p--;
    }
    if (k > 0) {
        cout << "-1\n";
    } else {
        // cout << a << "\n";
        for (int i:a) {
            cout << i << " ";
        }
        cout << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}