QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445152 | #8529. Balance of Permutation | ucup-team1198# | TL | 2ms | 11036kb | C++20 | 2.5kb | 2024-06-15 23:50:59 | 2024-06-15 23:50:59 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int N = 33;
__int128 dp[N][N][N][N * N];
__int128 calc_rest(vector<int> p, int n, int b) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= n; ++k)
fill(dp[i][j][k], dp[i][j][k] + n * n, 0);
}
}
int m = p.size();
int bal = 0;
int free = 0;
vector<int> kek(n);
vector<int> has_in(n);
for (int i = 0; i < m; ++i) {
++has_in[p[i]];
if (p[i] >= i) {
--kek[p[i]];
++kek[i];
} else {
++kek[p[i]];
--kek[i];
}
}
int sum = 0;
for (int i = 0; i < m; ++i) {
sum += bal;
if (kek[i] > 0)
bal += 1;
if (kek[i] < -1)
bal -= 1;
}
dp[m][bal][free][sum] = 1;
for (int i = m; i < n; ++i) {
for (int bal = 0; bal <= i; ++bal) {
for (int free = 0; free <= bal; ++free) {
for (int sum = 0; sum <= i * i; ++sum) {
__int128 ans = dp[i][bal][free][sum];
if (!ans)
continue;
if (has_in[i]) {
if (bal > 0) {
dp[i + 1][bal - 1][free][sum + bal] += ans * bal;
}
dp[i + 1][bal][free + 1][sum + bal] += ans;
} else {
if (bal > 0) {
dp[i + 1][bal - 1][free - 1][sum + bal] += ans * bal * free;
}
dp[i + 1][bal + 1][free + 1][sum + bal] += ans;
dp[i + 1][bal][free][sum + bal] += ans * (bal + free + 1);
}
}
}
}
}
return dp[n][0][0][b / 2];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, b;
string s;
cin >> n >> b >> s;
__int128 k = 0;
for (char c : s)
k = k * 10 + int(c - '0');
vector<int> ans;
vector<bool> free(n, true);
for (int i = 0; i < n; ++i) {
ans.emplace_back();
for (int j = 0; j < n; ++j) {
if (free[j]) {
ans[i] = j;
auto cur = calc_rest(ans, n, b);
if (cur < k) {
k -= cur;
} else {
free[j] = false;
break;
}
}
}
}
for (int x : ans)
cout << x + 1 << ' ';
cout << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11036kb
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