QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473048 | #8529. Balance of Permutation | GenshinImpactsFault# | TL | 2ms | 9788kb | C++14 | 2.3kb | 2024-07-11 21:27:32 | 2024-07-11 21:27:32 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const int N = 35;
const int M = N * N / 2;
int n, b, mxb;
__int128 m;
bool used[N];
__int128 f[2][N * N][N][N];
int a[N], cur_cnt = 0, cur_b = 0;
void read(__int128 &x) {
x = 0; char c = getchar();
for(; c < '0' || c > '9'; c = getchar());
for(; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + (c - '0');
}
void print(__int128 x) {
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
__int128 calc(int x, int cnt, int bb) {
for(int i = 0; i < 2; i++)
for(int j = M - mxb; j <= M + mxb; j++)
for(int k = 0; k <= n + 1; k++)
for(int h = 0; h <= n + 1; h++)
f[i][j][k][h] = 0;
f[x & 1][M + bb][cnt][0] = 1;
for(int i = x + 1; i <= n; i++) {
int cur = i & 1;
int pre = cur ^ 1;
for(int j = M - mxb; j <= M + mxb; j++)
for(int k = 0; k <= n; k++)
for(int h = 0; h <= n; h++) {
f[cur][j][k][h] = 0;
if(!used[i]) {
f[cur][j][k][h] += f[pre][j][k][h];
if(k && h) f[cur][j][k][h] += f[pre][j + 2 * i][k - 1][h - 1];
if(k) f[cur][j][k][h] += k * f[pre][j][k][h];
if(h) f[cur][j][k][h] += h * f[pre][j][k][h];
f[cur][j][k][h] += (h + 1) * (k + 1) * f[pre][j - 2 * i][k + 1][h + 1];
}
else {
if(h) f[cur][j][k][h] += f[pre][j][k][h - 1];
f[cur][j][k][h] += (k + 1) * f[pre][j - 2 * i][k + 1][h];
}
}
}
return f[n & 1][M + b][0][0];
}
int main() {
// int cur = clock();
cin >> n >> b; read(m);
for(int i = 1; i <= n; i++) mxb += abs(n - i + 1 - i);
// mxb = n * n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(used[j]) continue;
used[j] = 1, a[i] = j;
int nxt_cnt = 0;
for(int k = 1; k <= i; k++) if(!used[k]) ++nxt_cnt;
int nxt_b = cur_b;
if(j > i) nxt_b += -i;
if(j < i) nxt_b += i;
bool flag = 0;
for(int k = 1; k < i; k++) {
if(a[k] == i) flag = 1;
}
if(flag) nxt_b += i;
else if(a[i] != i) nxt_b -= i;
__int128 rem = calc(i, nxt_cnt, nxt_b);
if(rem >= m) {
cur_cnt = nxt_cnt, cur_b = nxt_b;
break;
}
else {
used[j] = 0;
m -= rem;
}
}
}
for(int i = 1; i <= n; i++) cout << a[i] << " ";
cout << "\n";
// cout << clock() - cur << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9788kb
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