QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451478#8529. Balance of PermutationHKOI0#TL 7745ms31348kbC++206.0kb2024-06-23 14:45:372024-06-23 14:45:38

Judging History

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

  • [2024-06-23 14:45:38]
  • 评测
  • 测评结果:TL
  • 用时:7745ms
  • 内存:31348kb
  • [2024-06-23 14:45:37]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
// #define int __int128_t
using i128 = __int128;

istream& operator>> (istream& in, __int128_t& x){
    string s; in >> s;
    x = 0; for (auto c : s) x = x * 10 + c - '0';
    return in;
}

ostream& operator<< (ostream& out, __int128_t x){
    string s; while (x) s.push_back('0' + x % 10), x /= 10; if (s.empty()) s = "0";
    reverse(all(s)); return out << s;
}

template<typename T> void chadd(T& x, T y){ x += y; }

const int B = 450 + 11;
i128 dp[31][31][B * 2];
i128 dp2[31][31][B * 2];
bool ok_a[31], ok_b[31];
i128 countPerm(int n, vector<int>& p, int len, int b){
    fill(ok_a + 1, ok_a + 31, true); fill(ok_b, ok_b + 31, true);
    fill(ok_a + 1, ok_a + 1 + len, false); for (int i = 0; i < len; i++) ok_b[p[i]] = false;
    // for (int i = 1; i <= n; i++) {
    //     cout << ok_a[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 1; i <= n; i++) {
    //     cout << ok_b[i] << ' ';
    // }
    // cout << endl;
    
    for (int r = 0; r <= 0; r++) {
        for (int b = 0; b < B * 2; b++) {
            dp[r][0][b] = dp[0][r][b] = 0;
        }
    }
    dp[0][0][B] = 1;
    for (int i = 0; i < n; i++) {
        for (int r = 0; r <= i + 1; r++) {
            for (int b = 0; b < B * 2; b++) {
                dp[r][i + 1][b] = dp[i + 1][r][b] = 0;
            }
        }
        auto copy_and_clear = [&] () {
            for (int rem_a = 0; rem_a <= i + 1; rem_a++) {
                for (int rem_b = 0; rem_b <= i + 1; rem_b++) {
                    for (int balance = 0; balance < B * 2; balance++) {
                        dp2[rem_a][rem_b][balance] = dp[rem_a][rem_b][balance];
                        dp[rem_a][rem_b][balance] = 0;
                    }
                }
            }
        };

        auto valid_balance = [&] (int x) {
            return 0 <= x && x < B * 2;
        };

        // top row
        if (ok_a[i + 1]) {
            copy_and_clear();
            for (int rem_a = 0; rem_a <= i; rem_a++) {
                for (int rem_b = 0; rem_b <= i; rem_b++) {
                    for (int balance = 0; balance < B * 2; balance++) {
                        i128 old_val = dp2[rem_a][rem_b][balance];
                        if (!old_val) continue;
                        // match backwards
                        if (rem_b && valid_balance(balance + (i + 1))) {
                            chadd(dp[rem_a][rem_b - 1][balance + (i + 1)], old_val * rem_b);
                        }
                        // match forwards
                        if (valid_balance(balance - (i - 1))) {
                            chadd(dp[rem_a + 1][rem_b][balance - (i + 1)], old_val);
                        }
                    }
                }
            }
        }
        // printf("Half\n");
        // for (int r = 0; r <= i + 1; r++) {
        //     for (int s = 0; s <= i + 1; s++) {
        //         for (int b = 0; b < B * 2; b++) {
        //             if (dp[r][s][b]) {
        //                 printf("dp[%lld][%lld][%lld][%lld] = %lld\n", (int64_t) (i + 1), (int64_t) r, (int64_t) s, (int64_t) b, (int64_t) dp[r][s][b]);
        //             }
        //         }
        //     }
        // }
        // bottom row
        if (ok_b[i + 1]) {
            copy_and_clear();
            for (int rem_a = 0; rem_a <= i; rem_a++) {
                for (int rem_b = 0; rem_b <= i; rem_b++) {
                    for (int balance = 0; balance < B * 2; balance++) {
                        i128 old_val = dp2[rem_a][rem_b][balance];
                        if (!old_val) continue;
                        // if (old_val) cout << rem_a << ' ' << rem_b << ' ' << balance << endl;
                        // match backwards
                        if (rem_a && valid_balance(balance + (i + 1))) {
                            chadd(dp[rem_a - 1][rem_b][balance + (i + 1)], old_val * rem_a);
                        }
                        // match forwards
                        if (valid_balance(balance - (i - 1))) {
                            chadd(dp[rem_a][rem_b + 1][balance - (i + 1)], old_val);
                        }
                    }
                }
            }
        }
        // printf("End\n");
        // for (int r = 0; r <= i + 1; r++) {
        //     for (int s = 0; s <= i + 1; s++) {
        //         for (int b = 0; b < B * 2; b++) {
        //             if (dp[r][s][b]) {
        //                 printf("dp[%lld][%lld][%lld][%lld] = %lld\n", (int64_t) (i + 1), (int64_t) r, (int64_t) s, (int64_t) b, (int64_t) dp[r][s][b]);
        //             }
        //         }
        //     }
        // }
    }

    // for (int i = B - b; i <= B + b; i++) {
    //     cout << dp[n][0][0][i] << ' ';
    // }
    // cout << endl;
    // cout << "RESULT " << dp[n][0][0][B + b] << endl;
    return dp[0][0][B + b];
}

void solve() {
    int n, b;
    i128 k;
    cin >> n >> b >> k;
    vector<int> p(n);
    vector<bool> rem(n + 1, true);
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!rem[j]) continue;
            // cout << "POSITION " << i << " VALUE " << j << " => K " << k << endl;
            p[i] = j;
            vector<int> x(p.begin(), p.begin() + i + 1);
            vector<int> y; 
            i128 cp = countPerm(n, p, i + 1, b - ((i + 1) - j < 0 ? j - (i + 1) : (i + 1) - j));
            if (k <= cp) {
                rem[j] = false;
                b -= ((i + 1) - j < 0 ? j - (i + 1) : (i + 1) - j);
                break;
            } else {
                k -= cp;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << p[i] << ' ';
    }
    cout << '\n';
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 12456kb

input:

6 6 6

output:

1 2 6 3 4 5 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 7385ms
memory: 31348kb

input:

30 300 3030303030303030303030

output:

1 2 3 4 9 23 20 28 24 16 21 17 27 29 8 26 25 30 19 18 22 12 7 13 6 10 5 15 14 11 

result:

ok 30 numbers

Test #3:

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

input:

1 0 1

output:

1 

result:

ok 1 number(s): "1"

Test #4:

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

input:

2 0 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #5:

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

input:

2 2 1

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #6:

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

input:

5 8 3

output:

1 5 4 2 3 

result:

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

Test #7:

score: 0
Accepted
time: 12ms
memory: 12284kb

input:

7 20 100

output:

3 6 7 4 1 5 2 

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 6ms
memory: 14324kb

input:

7 2 6

output:

2 1 3 4 5 6 7 

result:

ok 7 numbers

Test #9:

score: 0
Accepted
time: 7ms
memory: 12208kb

input:

7 24 1

output:

4 5 6 7 1 2 3 

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 9ms
memory: 14088kb

input:

7 22 360

output:

7 6 4 3 5 2 1 

result:

ok 7 numbers

Test #11:

score: 0
Accepted
time: 8ms
memory: 11988kb

input:

7 20 358

output:

5 7 2 4 6 3 1 

result:

ok 7 numbers

Test #12:

score: 0
Accepted
time: 58ms
memory: 16000kb

input:

10 48 10001

output:

7 5 8 9 6 10 3 4 1 2 

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 55ms
memory: 14360kb

input:

10 42 10101

output:

3 9 6 8 10 5 7 2 1 4 

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 3397ms
memory: 30532kb

input:

25 300 1

output:

7 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 8 9 10 11 12 13 

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 5122ms
memory: 28940kb

input:

25 300 283788388040048639877

output:

25 24 23 22 21 20 19 18 17 16 11 12 13 14 15 10 9 8 7 5 6 4 2 1 3 

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 5146ms
memory: 29384kb

input:

26 302 105773752969551707419545

output:

19 22 25 13 17 18 23 20 10 26 16 6 5 11 14 12 24 4 3 21 1 15 7 8 2 9 

result:

ok 26 numbers

Test #17:

score: 0
Accepted
time: 5560ms
memory: 30832kb

input:

27 308 8781128321749037280676555

output:

16 18 17 21 25 6 20 24 22 15 27 5 7 8 2 9 26 13 1 3 14 10 23 19 4 11 12 

result:

ok 27 numbers

Test #18:

score: 0
Accepted
time: 6432ms
memory: 30172kb

input:

28 304 806517199954337651602356955

output:

12 17 5 16 23 26 25 15 20 2 19 7 22 24 6 13 11 10 28 8 1 21 18 14 27 3 4 9 

result:

ok 28 numbers

Test #19:

score: 0
Accepted
time: 7745ms
memory: 30888kb

input:

29 322 40281026669581503094652149519

output:

16 21 10 25 17 29 9 28 2 8 26 27 22 4 3 5 18 14 19 1 23 20 15 11 13 7 6 12 24 

result:

ok 29 numbers

Test #20:

score: -100
Time Limit Exceeded

input:

30 400 46479902466857426153849991132

output:


result: