QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716700 | #8529. Balance of Permutation | ucup-team4992 | TL | 1ms | 3708kb | C++14 | 3.0kb | 2024-11-06 15:51:29 | 2024-11-06 15:51:29 |
Judging History
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';
}
int main() {
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);
const int ZERO = msum + 3;
vector<vector<vector<i128>>> dp(n - p + 3,
vector<vector<i128>>(n - p + 3, vector<i128>(2 * ZERO + 3)));
sort(lst.begin(), lst.end());
// for (auto [x, y] : lst) {
// cout << x << ' ';
// }
// cout << '\n';
dp[0][0][ZERO] = 1;
for (auto [x, tx] : lst) {
vector<vector<vector<i128>>> ndp(n - p + 3,
vector<vector<i128>>(n - p + 3, vector<i128>(2 * ZERO + 3)));
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];
}
}
dp = ndp;
}
// 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] << " ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
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