QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768972#7778. Turning Permutationucup-team5217#RE 0ms3680kbC++232.9kb2024-11-21 15:31:412024-11-21 15:31:41

Judging History

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

  • [2024-11-21 15:31:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3680kb
  • [2024-11-21 15:31:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define maxn 55

typedef __int128_t int128_t;

const int128_t LIM = 2e18;

bool vis[maxn];
int a[maxn];
int64_t f[maxn][maxn][3], g[2][maxn];
int64_t C[maxn][maxn];

void add(int64_t &a, int128_t w) { return a = min(LIM, a + min(w, LIM)), void(); }

void solve(void) {
    int n;
    int64_t k;
    cin >> n >> k;

    // if (n == 3) {
    //     if (k == 1)
    //         cout << "1 3 2" << endl;
    //     else if (k == 2)
    //         cout << "2 1 3" << endl;
    //     else if (k == 3)
    //         cout << "2 3 1" << endl;
    //     else if (k == 4)
    //         cout << "3 1 2" << endl;
    //     else
    //         cout << -1 << endl;
    //     return;
    // }

    f[0][0][0] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            for (int k = 0; k < 3; k++) {
                if (!f[i - 1][j][k]) continue;
                int128_t w = f[i - 1][j][k];
                add(f[i][j + 1][k], w);
                if (j >= 2) add(f[i][j - 1][k], w * j * (j - 1));
                if (j >= 1 && k >= 1) add(f[i][j - 1][k], w * j * k);
                if (k < 2) {
                    add(f[i][j][k + 1], w);
                    if (j >= 1) add(f[i][j - 1][k + 1], w * j);
                }
            }

    if ((f[n - 1][0][1] + f[n - 1][0][2]) * 2 < k) return cout << -1 << endl, void();

    for (int i = 1; i <= n; i++) g[0][i] = f[i][1][0], g[1][i] = f[i][0][1];

    auto getNum = [&](void) -> int128_t {
        int128_t ans = 1;
        int tot = 0;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = l;
            if (vis[l]) continue;
            while (r < n && !vis[r + 1]) r++;
            ans = min(LIM, ans * g[l == 1 || r == n][r - l + 1]);
            ans = min(LIM, ans * C[tot + r - l + 1][tot]), tot += r - l + 1;
        }
        return ans;
    };

    vis[0] = vis[n + 1] = true;
    for (a[1] = 1; a[1] <= n; a[1]++) {
        vis[a[1]] = true;
        int128_t w = getNum();
        if (k <= w) break;
        vis[a[1]] = false, k -= w;
    }

    assert(a[1] <= n);

    bool way = a[1] & 1;
    for (int i = 2; i <= n; i++) {
        for (a[i] = 1; a[i] <= n; a[i]++) {
            if (vis[a[i]]) continue;
            vis[a[i]] = true;
            if (((a[i] & 1) ^ way) && (!vis[a[i] - 1] || !vis[a[i] + 1])) continue;
            int128_t w = getNum();
            if (k <= w) break;
            vis[a[i]] = false, k -= w;
        }
        assert(a[i] <= n);
    }

    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    cout << endl;

    return;
}

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

    for (int i = 0; i < maxn; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) add(C[i][j], C[i - 1][j - 1] + C[i - 1][j]);
    }

    int _ = 1;
    while (_--) solve();

    return 0;
}

详细

Test #1:

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

input:

3 2

output:

2 1 3 

result:

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

Test #2:

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

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

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: 3616kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Runtime Error

input:

3 1

output:


result: