QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#444720 | #8529. Balance of Permutation | ucup-team3734# | TL | 277ms | 440412kb | C++23 | 5.9kb | 2024-06-15 20:58:12 | 2024-06-15 20:58:12 |
Judging History
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