QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444720#8529. Balance of Permutationucup-team3734#TL 277ms440412kbC++235.9kb2024-06-15 20:58:122024-06-15 20:58:12

Judging History

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

  • [2024-06-15 20:58:12]
  • 评测
  • 测评结果:TL
  • 用时:277ms
  • 内存:440412kb
  • [2024-06-15 20:58:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef __int128 i128;
typedef double lf;

u64 pack(int msk, int b) {
    return ((u64) msk << 10) | b;
}

int n;
unordered_map<u64, i128> mem;
i128 k;

pair<int, int> extr(int msk) {
    int mn = 0, mx = 0;
    int pos = n - __builtin_popcount(msk), rpos = n - 1;
    for (int i = 0; i < n; i++) {
        if ((msk >> i) & 1) {
            mn += abs(pos - i);
            mx += abs(rpos - i);
            pos++;
            rpos--;
        }
    }
    // if (mn > mx) {
    //     cerr << msk << ' ' << mn << ' ' << mx << '\n';
    // }
    // assert(mn <= mx);
    return {mn, mx};
}

i128 rec(int msk, int b) {
    auto [minb, maxb] = extr(msk);
    if (b < minb || b > maxb) {
        return 0;
    }
    if (msk == 0) {
        return b == 0 ? 1 : 0;
    }
    u64 val = pack(msk, b);
    if (mem.count(val)) {
        return mem[val];
    }
    i128 res = 0;
    int pos = n - __builtin_popcount(msk);
    for (int i = 0; i < n; i++) {
        if (((msk >> i) & 1) == 0) continue;
        res += rec(msk ^ (1 << i), b - abs(pos - i));
    }
    // cerr << msk << ' ' << b << ' ' << (u64)(res) << '\n';
    return mem[val] = res;
}

static constexpr int maxn = 30;
static constexpr int maxb = 500;

i128 dp[maxn + 1][2][maxn][maxn][maxb + 1];
bool has[maxn][2];

i128 calc(const vector<int> &pref, int need_b) {
    // int msk = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        has[i][0] = i >= (int) pref.size() ? 1 : 0;
        has[i][1] = 1;
    }
    for (int x : pref) {
        has[x][1] = 0;
    }
    for (int i = 0; i < (int) pref.size(); i++) {
        need_b -= abs(pref[i] - i);   
    }
    assert(need_b >= 0);
    assert(need_b <= maxb);
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int q = 0; q < 2; ++q) {
            for (int white = 0; white < n; ++white) {
                for (int black = 0; black < n; ++black) {
                    for (int b = 0; b <= need_b; ++b) {
                        auto cur_val = dp[i][q][white][black][b];
                        if (cur_val == 0) {
                            continue;
                        }
                        // cerr << i << " wh=" << white << " bl=" << black << " bal=" << b << " q=" << q << " ans=" << (u64) cur_val << '\n';
                        if (i == n) continue;
                        if (!has[i][q]) {
                            if (q == 0) {
                                dp[i][q + 1][white][black][b] += cur_val;
                            } else if (b + white + black <= need_b) {
                                dp[i + 1][0][white][black][b + white + black] += cur_val;
                            }
                            continue;
                        }
                        {
                            // begin segment
                            int nwhite = white + (q == 0 ? 1 : 0);
                            int nblack = black + (q == 1 ? 1 : 0);
                            if (q == 0) {
                                dp[i][q + 1][nwhite][nblack][b] += cur_val;
                            } else if (b + nwhite + nblack <= need_b) {
                                dp[i + 1][0][nwhite][nblack][b + nwhite + nblack] += cur_val;
                            }
                        }
                        {
                            // end segment
                            int nwhite = white - (q == 1 ? 1 : 0);
                            int nblack = black - (q == 0 ? 1 : 0);
                            if (nwhite >= 0 && nblack >= 0) {
                                int mult = q == 0 ? black : white;
                                if (q == 0) {
                                    dp[i][q + 1][nwhite][nblack][b] += cur_val * mult;
                                } else if (b + nwhite + nblack <= need_b) {
                                    dp[i + 1][0][nwhite][nblack][b + nwhite + nblack] += cur_val * mult;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    auto res = dp[n][0][0][0][need_b];
    // cerr << "res = " << (u64) res << endl;
    // cerr << "==============================================" << endl;
    return res;
}

void readk() {
    string s;
    cin >> s;
    k = 0;
    for (char c : s) {
        k = k * 10 + c - '0';
    }
    k--;
}

void solve() {
    int b;
    cin >> n >> b;
    readk();
    
    // mem.reserve(1 << 25);
    // vector<int> a(n, -1);
    // int msk = (1 << n) - 1;
    // assert(k < rec(msk, b));
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         if (((msk >> j) & 1) == 0) continue;
    //         i128 cur = rec(msk ^ (1 << j), b - abs(i - j));
    //         if (k < cur) {
    //             a[i] = j;
    //             msk ^= 1 << j;
    //             b -= abs(i - j);
    //             break;
    //         } else {
    //             k -= cur;
    //         }
    //     }
    // }


    int msk = (1 << n) - 1;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; ++j) {
            if (((msk >> j) & 1) == 0) continue;
            a.push_back(j);
            i128 cur = calc(a, b);
            if (k < cur) {
                msk ^= 1 << j;
                break;
            } else {
                k -= cur;
                a.pop_back();
            }
        }
    }
    for (int x : a) {
        cout << x + 1 << ' ';
    }
    cout << '\n';
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 277ms
memory: 440412kb

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: