QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525908#6339. CookiesQwerty1232#0 335ms883488kbC++234.7kb2024-08-21 03:05:102024-08-21 03:05:11

Judging History

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

  • [2024-08-21 03:05:11]
  • 评测
  • 测评结果:0
  • 用时:335ms
  • 内存:883488kb
  • [2024-08-21 03:05:10]
  • 提交

answer

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>

// constexpr int N = 1.5e4 + 5;

void chmin(auto& a, auto b) {
    a = std::min(a, b);
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> input(n);
    for (auto& i : input) {
        std::cin >> i;
    }
    int m;
    std::cin >> m;
    std::vector<int> sz(m);
    for (auto& i : sz) {
        std::cin >> i;
    }

    int mx = std::max_element(input.begin(), input.end()).operator*();
    int sm = std::accumulate(input.begin(), input.end(), 0);

    std::vector<int> shit(input.begin(), input.end());
    std::sort(shit.rbegin(), shit.rend());
    std::vector<int> shit_suf(n + 1);
    for (int i = n - 1, s = 0; i >= 0; i--) {
        s += shit[i], shit_suf[i] = s;
    }

    std::vector<std::vector<std::vector<int>>> dp(n);
    for (int i = 0; i < n; i++) {
        dp[i] = std::vector<std::vector<int>>(std::min<int>(mx, (sm / (i + 1))) + 1, std::vector<int>(shit_suf[i] + 1, sm + 5));
    }

    dp[n - 1][0][0] = 0;

    for (int i = n - 1; i >= 0; i--) {
        bool bx = std::binary_search(sz.begin(), sz.end(), i + 1);
        if (bx) {
            for (int j = 0; j + 1 < dp[i].size(); j++) {
                for (int k = 0; k < dp[i][j].size(); k++) {
                    int k2 = k + 1;
                    if (k2 < dp[i][j + 1].size()) {
                        chmin(dp[i][j + 1][k2], dp[i][j][k] + 1);
                    }
                }
            }
        }
        if (i > 0) {
            for (int j = 0; j < dp[i].size(); j++) {
                for (int k = 0; k < dp[i][j].size(); k++) {
                    int k2 = k + j;
                    if (k2 < dp[i - 1][j].size()) {
                        chmin(dp[i - 1][j][k2], dp[i][j][k]);
                    }
                }
            }
        }
    }

    std::vector<int> bx_sz;
    {
        std::array<int, 3> min = {sm + 1, -1, -1};
        for (int k = 0; k < dp[0].size(); k++) {
            if (sm < dp[0][k].size()) {
                min = std::min(min, std::array<int, 3>{dp[0][k][sm], k, sm});
            }
        }
        std::pair<int, int> pos(min[1], min[2]);
        if (min.front() > sm || pos.first == -1) {
            std::cout << "-1\n";
            return 0;
        }

        for (int i = 0; i < n; i++) {
            bool bx = std::binary_search(sz.begin(), sz.end(), i + 1);
            if (bx) {
                for (int j = (int)dp[i].size() - 1; j > 0; j--) {
                    for (int k = 0; k < dp[i][j].size(); k++) {
                        if (j != pos.first || k != pos.second) {
                            continue;
                        }
                        int k2 = k - 1;
                        if (0 <= k2 && k2 < dp[i][j - 1].size() && dp[i][j - 1][k2] + 1 == dp[i][j][k]) {
                            pos.first--, pos.second--;
                            bx_sz.push_back(i + 1);
                        }
                    }
                }
            }
            if (i + 1 < n) {
                for (int j = 0; j < dp[i].size(); j++) {
                    for (int k = 0; k < dp[i][j].size(); k++) {
                        if (j != pos.first || k != pos.second) {
                            continue;
                        }
                        int k2 = k - j;
                        if (0 <= k2 && k2 < dp[i + 1][j].size() && dp[i + 1][j][k2] == dp[i][j][k]) {
                            pos.second -= j;
                        }
                    }
                }
            }
        }
    }

    // !

    int q = bx_sz.size();
    std::sort(bx_sz.rbegin(), bx_sz.rend());

    std::priority_queue<std::pair<int, int>> heap;
    for (int i = 0; i < n; i++) {
        heap.push({input[i], i});
    }

    std::vector<std::vector<int>> ans(q);
    for (int i = 0; i < q; i++) {
        std::vector<std::pair<int, int>> vec(bx_sz[i]);
        ans[i].resize(bx_sz[i]);
        for (int j = 0; j < bx_sz[i]; j++) {
            assert(heap.size());
            vec[j] = heap.top(), heap.pop(), vec[j].first--, ans[i][j] = vec[j].second;
        }
        for (auto p : vec) {
            if (p.first > 0) {
                heap.push(p);
            }
        }
    }

    std::cout << ans.size() << "\n";
    for (auto& vec : ans) {
        std::cout << vec.size();
        std::sort(vec.begin(), vec.end());
        for (auto i : vec) {
            std::cout << " " << i + 1;
        }
        std::cout << std::endl;
    }

    return 0;
}

/*


5 5 2 2 2 2 0
5 4 4 2 1 1 1


5 4 4 2 1 1 1
4 3 3 1 1 0 0
4 3 3 1 1 0 0





*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 0ms
memory: 3608kb

input:

1
1
1
1

output:

1
1 1

result:

ok good!

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3476kb

input:

2
1 1
1
1

output:

-1

result:

wrong answer you didn't find a solution but jury did

Subtask #2:

score: 0
Wrong Answer

Test #28:

score: 7
Accepted
time: 0ms
memory: 3628kb

input:

1
15
1
1

output:

15
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

result:

ok good!

Test #29:

score: 7
Accepted
time: 0ms
memory: 4628kb

input:

1
500
1
1

output:

500
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
...

result:

ok good!

Test #30:

score: 7
Accepted
time: 11ms
memory: 38924kb

input:

1
3000
1
1

output:

3000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

result:

ok good!

Test #31:

score: 7
Accepted
time: 335ms
memory: 883488kb

input:

1
15000
1
1

output:

15000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 ...

result:

ok good!

Test #32:

score: 0
Wrong Answer
time: 0ms
memory: 3828kb

input:

2
2 1
1
1

output:

-1

result:

wrong answer you didn't find a solution but jury did

Subtask #3:

score: 0
Wrong Answer

Test #45:

score: 12
Accepted
time: 0ms
memory: 3620kb

input:

2
7 8
2
1 2

output:

8
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
1 2

result:

ok good!

Test #46:

score: 12
Accepted
time: 0ms
memory: 3628kb

input:

3
5 4 6
2
2 3

output:

6
3 1 2 3
3 1 2 3
3 1 2 3
2 1 3
2 2 3
2 1 3

result:

ok good!

Test #47:

score: 12
Accepted
time: 0ms
memory: 3832kb

input:

3
4 2 9
3
1 2 3

output:

9
3 1 2 3
3 1 2 3
2 1 3
2 1 3
1 3
1 3
1 3
1 3
1 3

result:

ok good!

Test #48:

score: 12
Accepted
time: 0ms
memory: 3824kb

input:

4
3 5 4 3
2
3 4

output:

5
3 2 3 4
3 1 2 3
3 2 3 4
3 1 2 4
3 1 2 3

result:

ok good!

Test #49:

score: 12
Accepted
time: 0ms
memory: 3560kb

input:

4
1 4 5 5
3
1 3 4

output:

5
3 2 3 4
3 2 3 4
3 2 3 4
3 2 3 4
3 1 3 4

result:

ok good!

Test #50:

score: 12
Accepted
time: 0ms
memory: 3536kb

input:

4
3 3 6 3
3
2 3 4

output:

6
4 1 2 3 4
3 2 3 4
2 1 3
2 3 4
2 2 3
2 1 3

result:

ok good!

Test #51:

score: 12
Accepted
time: 0ms
memory: 3608kb

input:

5
4 3 3 3 1
3
2 4 5

output:

4
4 1 2 3 4
4 1 2 3 4
4 1 3 4 5
2 1 2

result:

ok good!

Test #52:

score: 12
Accepted
time: 0ms
memory: 3608kb

input:

5
4 3 3 3 2
3
3 4 5

output:

4
5 1 2 3 4 5
4 1 2 3 4
3 1 4 5
3 1 2 3

result:

ok good!

Test #53:

score: 0
Wrong Answer
time: 0ms
memory: 3824kb

input:

5
4 4 4 2 1
3
2 4 5

output:

-1

result:

wrong answer you didn't find a solution but jury did

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%