QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#447298#8529. Balance of Permutationucup-team3924WA 1402ms29668kbC++204.5kb2024-06-18 09:14:202024-06-18 09:14:20

Judging History

你现在查看的是最新测评结果

  • [2024-06-18 09:14:20]
  • 评测
  • 测评结果:WA
  • 用时:1402ms
  • 内存:29668kb
  • [2024-06-18 09:14:20]
  • 提交

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'