QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#444214 | #8529. Balance of Permutation | ucup-team3678# | WA | 85ms | 30100kb | C++14 | 3.2kb | 2024-06-15 17:48:49 | 2024-06-15 17:48:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
__int128 f[N][N][N][N * N];
int val[N], vis[N], hv[N];
signed main() {
int n, m;
__int128 k = 0;
scanf("%d%d", &n, &m);
string s; cin >> s;
for (auto c : s) k = k * 10 + c - '0';
for (int i = 1; i <= n; ++i) {
val[i] = 1;
while (1) {
if (vis[val[i]]) {
++val[i]; continue;
}
__int128 t = 0;
for (int j = 1; j <= n; ++j) hv[j] = 0;
for (int j = 1; j <= i; ++j) {
t += max(val[j] - j, 0), hv[val[j]] = 1;
}
reverse(hv + i + 1, hv + n + 1);
f[i][0][0][0] = 1;
int s2 = 0;
for (int j = i + 1; j <= n; ++j) {
s2 += hv[j];
for (int k = 0; k <= s2; ++k) {
for (int l = 0; k + l <= j - i; ++l) {
for (int p = 0; p <= (m >> 1) - t; ++p) {
if (hv[j]) {
f[j][k][l][p + l] += f[j - 1][k][l][p];
f[j][k + 1][l][p + l] += f[j - 1][k][l][p];
f[j][k][l][p + l] += f[j - 1][k][l][p] * k;
if (l) f[j][k + 1][l - 1][p + 1] += f[j - 1][k][l][p] * l;
if (k) f[j][k - 1][l][p + l] += f[j - 1][k][l][p] * k * k;
if (l) f[j][k][l - 1][p + l] += f[j - 1][k][l][p] * l * l;
if (k && l) f[j][k - 1][l][p + l] += f[j - 1][k][l][p] * k * l;
if (k && l) f[j][k][l - 1][p + l] += f[j - 1][k][l][p] * k * l;
} else {
f[j][k][l][p + l] += f[j - 1][k][l][p];
f[j][k][l + 1][p + l] += f[j - 1][k][l][p];
if (k) f[j][k - 1][l + 1][p + l] += f[j - 1][k][l][p] * k;
f[j][k][l][p + 1] += f[j - 1][k][l][p] * l;
f[j][k][l][p + l] += f[j - 1][k][l][p] * (k + l);
if (k) f[j][k - 1][l][p + l] += f[j - 1][k][l][p] * k * k;
if (l) f[j][k][l - 1][p + l] += f[j - 1][k][l][p] * l * l;
if (k && l) f[j][k - 1][l][p + l] += f[j - 1][k][l][p] * k * l;
if (k && l) f[j][k][l - 1][p + l] += f[j - 1][k][l][p] * k * l;
}
}
}
}
}
__int128 s = f[n][0][0][(m >> 1) - t];
s2 = 0;
for (int j = i + 1; j <= n + 1; ++j) {
for (int k = 0; k <= s2; ++k) {
for (int l = 0; k + l <= j - i; ++l) {
for (int p = 0; p <= (m >> 1) - t; ++p) {
f[j - 1][k][l][p] = 0;
}
}
}
}
if (s >= k) {
break;
}
k -= s, ++val[i];
}
vis[val[i]] = 1;
printf("%d%c", val[i], " \n"[i == n]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5956kb
input:
6 6 6
output:
1 2 6 3 4 5
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 85ms
memory: 30100kb
input:
30 300 3030303030303030303030
output:
1 2 3 4 15 6 5 7 8 9 10 11 12 13 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1398985
result:
wrong answer 5th numbers differ - expected: '9', found: '15'