QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716811#8529. Balance of Permutationucup-team4992TL 0ms20252kbC++143.4kb2024-11-06 16:06:152024-11-06 16:06:15

Judging History

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

  • [2024-11-06 16:06:15]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:20252kb
  • [2024-11-06 16:06:15]
  • 提交

answer

#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;
using i128 = __int128;
using i64 = long long;
using pii = pair<int, int>;
void read(i128& x) {
    char ch = getchar();
    while (isspace(ch))
        ch = getchar();
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}
void write(i128 x) {
    string s;
    do {
        s += char('0' + x % 10);
        x /= 10;
    } while (x);
    reverse(s.begin(), s.end());
    cout << s << '\n';
}
const int ZERO = 1000;
i128 dp[40][40][2030], ndp[40][40][2030];
int main() {
    double prev = clock();
    int n, b;
    i128 k;
    cin >> n >> b;
    read(k);
    vector<int> ans(n + 5), usd(n + 5);
    auto try_use = [&](int p, int q) {
        int suma = 0, sumb = 0;
        vector<pii> lst;
        for (int i = p + 1; i <= n; i++) {
            suma += i;
            lst.push_back({i, 0});
        }
        for (int i = 1; i <= n; i++) {
            if (!usd[i] && i != q) {
                sumb += i;
                lst.push_back({i, 1});
            }
        }
        const int msum = max(suma, sumb);
        sort(lst.begin(), lst.end());
        // for (auto [x, y] : lst) {
        //     cout << x << ' ';
        // }
        // cout << '\n';
        for (int i = 0; i <= n - p; i++)
            for (int j = 0; j <= n - p; j++)
                for (int s = -msum; s <= msum; s++)
                    dp[i][j][ZERO + s] = 0;
        dp[0][0][ZERO] = 1;
        for (auto [x, tx] : lst) {
            for (int i = 0; i <= n - p; i++)
                for (int j = 0; j <= n - p; j++)
                    for (int s = -msum; s <= msum; s++)
                        ndp[i][j][ZERO + s] = 0;
            for (int i = 0; i <= n - p; i++)
                for (int j = 0; j <= n - p; j++)
                    for (int s = -msum; s <= msum; s++) {
                        if (tx == 0) {
                            if (s - x >= -msum) ndp[i + 1][j][ZERO + s - x] += dp[i][j][ZERO + s];
                            if (j) ndp[i][j - 1][ZERO + s + x] += j * dp[i][j][ZERO + s];
                        } else {
                            if (s - x >= -msum) ndp[i][j + 1][ZERO + s - x] += dp[i][j][ZERO + s];
                            if (i) ndp[i - 1][j][ZERO + s + x] += i * dp[i][j][ZERO + s];
                        }
                    }
            for (int i = 0; i <= n - p; i++)
                for (int j = 0; j <= n - p; j++)
                    for (int s = -msum; s <= msum; s++)
                        dp[i][j][ZERO + s] = ndp[i][j][ZERO + s];
        }
        // for (int i = -msum; i <= msum; i++) {
        //     cout << i64(dp[0][0][ZERO + i]) << ' ';
        // }
        // cout << '\n';
        return dp[0][0][ZERO + b - abs(p - q)];
    };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (!usd[j]) {
                auto res = try_use(i, j);
                // write(res);
                if (res < k)
                    k -= res;
                else {
                    ans[i] = j;
                    usd[j] = 1;
                    b -= abs(i - j);
                    break;
                }
            }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    double cur = clock();
    // cout << "time=" << (cur - prev) / CLOCKS_PER_SEC << '\n';
    return 0;
}

详细

Test #1:

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

input:

6 6 6

output:

1 2 6 3 4 5 

result:

ok 6 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

30 300 3030303030303030303030

output:


result: