QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#447298 | #8529. Balance of Permutation | ucup-team3924 | WA | 1402ms | 29668kb | C++20 | 4.5kb | 2024-06-18 09:14:20 | 2024-06-18 09:14:20 |
Judging History
answer
#include<bits/stdc++.h>
const int MAX_N = 30;
const int OFFSET = MAX_N * MAX_N;
__int128 dp[1 + MAX_N][1 + MAX_N][OFFSET + 1 + OFFSET];
__int128& getdp(int N, int chains, int sum) {
return dp[N][chains][sum + OFFSET];
}
__int128 read_i128(std::string str) {
__int128 res = 0;
for (auto it: str)
res = res * 10 + it - '0';
return res;
}
std::string to_string(__int128 val) {
std::string res;
if (val == 0) return "0";
while (val > 0) {
res.push_back(val % 10 + '0');
val /= 10;
}
std::reverse(res.begin(), res.end());
return res;
}
__int128 count_permutations(std::vector<int>& pref, int n, int N, int sum) {
std::vector<bool> marked(N);
int temp_sum = 0;
int temp_chains = 0;
for (int i = 0; i < n; i++) {
marked[pref[i]] = true;
temp_sum += std::abs(i - pref[i]);
if (pref[i] >= n)
temp_chains++;
}
for (int i = 0; i < n; i++)
if (!marked[i])
temp_sum -= i;
for (int i = 0; i <= N; i++)
for (int j = -OFFSET; j <= OFFSET; j++)
getdp(n, i, j) = 0;
getdp(n, temp_chains, temp_sum) = 1;
int invalid_chain = temp_chains;
for (int i = n + 1; i <= N; i++) {
if (marked[i - 1]) invalid_chain--;
for (int chains = invalid_chain; chains <= N; chains++) {
for (int sum = -OFFSET; sum <= OFFSET; sum++) {
getdp(i, chains, sum) = 0;
if (marked[i - 1]) {
// This element already is included in a chain. I can either close that cycle or
// merge this to some other chain
if (sum - (i - 1) >= -OFFSET && chains + 1 <= N)
getdp(i, chains, sum) += getdp(i - 1, chains + 1, sum - (i - 1)) * (chains + 1);
// Keep this the way it is, its head will be open for the future
if (sum + (i - 1) <= OFFSET)
getdp(i, chains, sum) += getdp(i - 1, chains, sum + (i - 1));
} else {
// Keep this a fixed point
getdp(i, chains, sum) += getdp(i - 1, chains, sum);
// append this to some chain in either direction, but some of the chains are still
// waiting for some future element, therefore are invalid, so they must be subtracted.
if (chains >= invalid_chain)
getdp(i, chains, sum) += getdp(i - 1, chains, sum) * (2 * chains - invalid_chain);
// Add this as a standalone chain
if (chains > 0 && sum + 2 * (i - 1) <= OFFSET)
getdp(i, chains, sum) += getdp(i - 1, chains - 1, sum + 2 * (i - 1));
// Close one of the chains into a cycle. We can't close a chain that still waits for an element.
if (chains + 1 <= N && sum - 2 * (i - 1) >= -OFFSET && chains + 1 - invalid_chain > 0) {
getdp(i, chains, sum) += getdp(i - 1, chains + 1, sum - 2 * (i - 1)) * (chains + 1 - invalid_chain);
getdp(i, chains, sum) += getdp(i - 1, chains + 1, sum - 2 * (i - 1)) * (chains + 1 - invalid_chain) * chains;
}
}
}
}
}
return getdp(N, 0, sum);
}
int main(){
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int n, b;
std::string _k;
__int128 k;
std::cin >> n >> b >> _k;
k = read_i128(_k);
if (b % 2 == 1) {
std::cout << 0;
return 0;
}
std::vector<int> remaining(n);
std::vector<int> res(n);
for (int i = 0; i < remaining.size(); i++)
remaining[i] = i;
for (int i = 0; i < n; i++) {
int pos = 0;
bool compute;
do {
res[i] = remaining[pos];
__int128 t = count_permutations(res, i + 1, n, b);
compute = false;
if (t < k) {
k -= t;
pos++;
compute = true;
}
} while (compute);
while (pos + 1 < remaining.size()) {
remaining[pos] = remaining[pos + 1];
pos++;
}
remaining.resize(remaining.size() - 1);
}
for (int i = 0; i < n; i++)
std::cout << res[i] + 1 << " ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9956kb
input:
6 6 6
output:
1 2 6 3 4 5
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1402ms
memory: 29668kb
input:
30 300 3030303030303030303030
output:
1 2 3 4 9 23 20 28 24 16 21 17 27 29 8 26 25 30 19 18 22 12 7 13 6 10 5 15 14 11
result:
ok 30 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 0 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
2 0 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
2 2 1
output:
2 1
result:
ok 2 number(s): "2 1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
5 8 3
output:
1 5 4 2 3
result:
ok 5 number(s): "1 5 4 2 3"
Test #7:
score: 0
Accepted
time: 8ms
memory: 10092kb
input:
7 20 100
output:
3 6 7 4 1 5 2
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 9924kb
input:
7 2 6
output:
2 1 3 4 5 6 7
result:
ok 7 numbers
Test #9:
score: 0
Accepted
time: 8ms
memory: 9940kb
input:
7 24 1
output:
4 5 6 7 1 2 3
result:
ok 7 numbers
Test #10:
score: 0
Accepted
time: 9ms
memory: 9760kb
input:
7 22 360
output:
7 6 4 3 5 2 1
result:
ok 7 numbers
Test #11:
score: 0
Accepted
time: 4ms
memory: 9876kb
input:
7 20 358
output:
5 7 2 4 6 3 1
result:
ok 7 numbers
Test #12:
score: 0
Accepted
time: 26ms
memory: 13824kb
input:
10 48 10001
output:
7 5 8 9 6 10 3 4 1 2
result:
ok 10 numbers
Test #13:
score: 0
Accepted
time: 28ms
memory: 12120kb
input:
10 42 10101
output:
3 9 6 8 10 5 7 2 1 4
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 848ms
memory: 26876kb
input:
25 300 1
output:
7 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 8 9 10 11 12 13
result:
ok 25 numbers
Test #15:
score: 0
Accepted
time: 1336ms
memory: 22172kb
input:
25 300 283788388040048639877
output:
25 24 23 22 21 20 19 18 17 16 11 12 13 14 15 10 9 8 7 5 6 4 2 1 3
result:
ok 25 numbers
Test #16:
score: 0
Accepted
time: 1291ms
memory: 28356kb
input:
26 302 105773752969551707419545
output:
19 22 25 13 17 18 23 20 10 26 16 6 5 11 14 12 24 4 3 21 1 15 7 8 2 9
result:
ok 26 numbers
Test #17:
score: -100
Wrong Answer
time: 1377ms
memory: 28528kb
input:
27 308 8781128321749037280676555
output:
16 18 17 21 25 6 20 14 26 27 22 8 7 12 23 13 9 11 15 1 19 4 3 24 2 5 10
result:
wrong answer 8th numbers differ - expected: '24', found: '14'