QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446098 | #8529. Balance of Permutation | ucup-team3215 | TL | 0ms | 0kb | C++20 | 1.5kb | 2024-06-16 21:25:31 | 2024-06-16 21:25:31 |
answer
#include <bits/stdc++.h>
using namespace std;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
u128 mem[30][30][30][256];
u16 mark[30][30][30][256], ct;
int n, b;
u128 cnt(int l, int c, int d, int b, u32 m) {
if (b < c * (c - 1) / 2 || b > (n - l) * (n - l - 1) / 2 || max(c, d) + l > n) return 0;
if (l == n - 1) return 1;
if (mark[l][c][d][b] == ct) return mem[l][c][d][b];
mark[l][c][d][b] = ct;
u128 ans{};
if ((m & 1 << l) && d) {
ans += cnt(l + 1, c - 1, d - 1, b - c + 1, m) * c * d;
ans += cnt(l + 1, c, d, b - c, m) * d;
}
if (c += m >> l & 1) ans += cnt(l + 1, c - 1, d, b - c + 1, m) * c;
ans += cnt(l + 1, c, d + 1, b - c, m);
return mem[l][c -= m >> l & 1][d][b] = ans;
}
u128 cnt(int l, int b, u32 m) {
int c = 0;
for (int i = 0; i < l; ++i) if (m & 1 << i) {
++c;
b -= l - i;
m ^= 1 << i;
}
++ct;
auto ans = cnt(l, c, 0, b, m);
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> b; b /= 2;
u128 k{};
for (char c; cin >> c && isdigit(c); ) k = k * 10 + c - '0';
u32 ans[30], l = 0, m = (1 << n) - 1;
while (l < n) {
for (int i = 0; i < n; ++i) if (m & 1 << i) if (auto t = cnt(l + 1, b - max((int)l - i, {}), m - (1 << i)); t >= k) {
b -= max((int)l - i, {});
ans[l++] = i + 1;
m -= 1 << i;
break;
} else k -= t;
}
for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
6 6 6