QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#482738#7778. Turning Permutation_LAP_WA 0ms3888kbC++142.6kb2024-07-17 21:07:072024-07-17 21:07:08

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 21:07:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2024-07-17 21:07:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 55;
const __int128 maxv = (long long)1e18 + 1;
int n; long long k;

long long f[N][3][3], binom[N][N];
// 0:= 无限制
// 1:= x < y
// 2:= x > y

set<int> Set;
inline long long check(int p) {
    if(Set.count(p - 1) && !Set.count(p + 1) && p != n) return 0;
    Set.insert(p);
    vector<int> vec(Set.begin(), Set.end());
    long long res = 1;
    if(vec[0] != 1) res = min(maxv, (__int128)res * f[vec[0] - 1][0][1]);
    for(int i = 1; i < vec.size(); i ++)
        res = min(maxv, (__int128)res * f[vec[i] - vec[i - 1] - 1][2][1]);
    if(vec.back() != n) res = min(maxv, (__int128)res * f[n - vec.back()][2][0]);
    int lst = n - Set.size();
    res = min(maxv, (__int128)res * binom[lst][vec[0] - 1]), lst -= vec[0] - 1;
    for(int i = 1; i < vec.size(); i ++)
        res = min(maxv, (__int128)res * binom[lst][vec[i] - vec[i - 1] - 1]), lst -= vec[i] - vec[i - 1] - 1;
    res = min(maxv, (__int128)res * binom[lst][n - vec.back()]);
    Set.erase(p);
    return res;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> k;
    binom[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        binom[i][0] = 1;
        for(int j = 1; j <= i; j ++)
            binom[i][j] = min((long long)maxv, binom[i - 1][j - 1] + binom[i - 1][j]);
    }
    for(int i = 0; i <= 2; i ++)
        for(int j = 0; j <= 2; j ++)
            f[1][i][j] = f[0][i][j] = 1;
    for(int i = 2; i <= n; i ++) {
        for(int a = 0; a <= 2; a ++) for(int b = 0; b <= 2; b ++) {
            __int128 val = 0;
            for(int x = 1; x <= i; x ++) {
                if(a == 1 && x == 2) continue;
                if(a == 2 && x == 1) continue;
                if(b == 1 && x == i) continue;
                if(b == 2 && x == i - 1) continue;
                val += min(maxv, (__int128)f[x - 1][a][1] * f[i - x][2][b]) * binom[i - 1][x - 1];
                val = min(val, maxv);
            }
            f[i][a][b] = val;
        }
    }

    if(f[n][0][0] >= k) {
        vector<int> ans;
        for(int i = 1; i <= n; i ++) {
            int x = 1;
            while(true) {
                while(Set.count(x)) x ++;
                long long c = check(x);
                if(c >= k) break;
                else k -= c, x ++;
            }
            Set.insert(x);
            ans.emplace_back(x);
        }
        for(int i = 0; i < ans.size(); i ++)
            cout << ans[i] << " \n"[i + 1 == ans.size()];
    } else cout << "-1" << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3 2

output:

2 1 3

result:

ok 3 number(s): "2 1 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

4 6

output:

3 1 2 4

result:

ok 4 number(s): "3 1 2 4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

3 1

output:

1 3 2

result:

ok 3 number(s): "1 3 2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3 10

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3 52

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

3 756

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

3 7721

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5 1

output:

1 3 2 5 4

result:

ok 5 number(s): "1 3 2 5 4"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

5 8

output:

2 4 1 3 5

result:

ok 5 number(s): "2 4 1 3 5"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5 85

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5 846

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

5 6957

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

8 1

output:

1 3 2 5 4 7 6 8

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

8 7

output:

1 3 2 5 7 8 4 6

result:

ok 8 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

8 71

output:

1 3 7 5 4 2 6 8

result:

ok 8 numbers

Test #18:

score: -100
Wrong Answer
time: 0ms
memory: 3688kb

input:

8 863

output:

3 2 7 5 1 6 8 4

result:

wrong answer 2nd numbers differ - expected: '5', found: '2'