QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#525915#6339. CookiesQwerty1232Compile Error//C++234.7kb2024-08-21 03:17:282024-08-21 03:17:28

Judging History

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

  • [2024-08-21 03:17:28]
  • 评测
  • [2024-08-21 03:17:28]
  • 提交

answer

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

// constexpr int N = 1.5e4 + 5;

template <typename T>
void chmin(T& a, const T& 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<short>>> dp(n);

    for (int i = n - 1; i < n; i++) {
        dp[i] = std::vector<std::vector<short>>(std::min<int>(1e9, (sm / (i + 1))) + 1, std::vector<short>(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<short>(dp[i][j + 1][k2], dp[i][j][k] + 1);
                    }
                }
            }
        }
        if (i > 0) {
            dp[i - 1] = std::vector<std::vector<short>>(std::min<int>(1e9, (sm / (i - 1 + 1))) + 1, std::vector<short>(shit_suf[i - 1] + 1, sm + 5));

            for (int j = 0; j < dp[i].size(); j++) {
                while (dp[i][j].size() && dp[i][j].back() > sm) {
                    dp[i][j].pop_back();
                }
                dp[i][j].shrink_to_fit();

                for (int k = 0; k < dp[i][j].size(); k++) {
                    int k2 = k + j;
                    if (k2 < dp[i - 1][j].size()) {
                        chmin<short>(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--) {
                    if (j != pos.first) {
                        continue;
                    }
                    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) {
                pos.second -= pos.first;
            }
        }
    }

    // !

    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





*/

詳細信息

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~