QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716811 | #8529. Balance of Permutation | ucup-team4992 | TL | 0ms | 20252kb | C++14 | 3.4kb | 2024-11-06 16:06:15 | 2024-11-06 16:06:15 |
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';
}
const int ZERO = 1000;
i128 dp[40][40][2030], ndp[40][40][2030];
int main() {
double prev = clock();
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);
sort(lst.begin(), lst.end());
// for (auto [x, y] : lst) {
// cout << x << ' ';
// }
// cout << '\n';
for (int i = 0; i <= n - p; i++)
for (int j = 0; j <= n - p; j++)
for (int s = -msum; s <= msum; s++)
dp[i][j][ZERO + s] = 0;
dp[0][0][ZERO] = 1;
for (auto [x, tx] : lst) {
for (int i = 0; i <= n - p; i++)
for (int j = 0; j <= n - p; j++)
for (int s = -msum; s <= msum; s++)
ndp[i][j][ZERO + s] = 0;
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];
}
}
for (int i = 0; i <= n - p; i++)
for (int j = 0; j <= n - p; j++)
for (int s = -msum; s <= msum; s++)
dp[i][j][ZERO + s] = ndp[i][j][ZERO + s];
}
// 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] << " ";
double cur = clock();
// cout << "time=" << (cur - prev) / CLOCKS_PER_SEC << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 20252kb
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