QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444214#8529. Balance of Permutationucup-team3678#WA 85ms30100kbC++143.2kb2024-06-15 17:48:492024-06-15 17:48:49

Judging History

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

  • [2024-06-15 17:48:49]
  • 评测
  • 测评结果:WA
  • 用时:85ms
  • 内存:30100kb
  • [2024-06-15 17:48:49]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'