제출 #1112643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112643		MisterReaper	Gift (IZhO18_nicegift)	C++17	100 / 100	473 ms	116908 KiB

nicegift

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "../../../debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K;
    std::cin >> N >> K;
    std::vector<i64> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    i64 sum = std::accumulate(A.begin(), A.end(), 0LL);
    if (sum % K != 0) {
        std::cout << "-1\n";
        return 0;
    }

    i64 gsiz = sum / K;

    int cur = 0;
    i64 now = 0;
    std::vector<std::deque<std::pair<i64, i64>>> g(K);
    for (int i = 0; i < N; ++i) {
        if (A[i] > gsiz) {
            std::cout << "-1\n";
            return 0;
        }
        if (now + A[i] > gsiz) {
            g[cur].emplace_back(gsiz - now, i);
            ++cur;
            now = now + A[i] - gsiz;
            g[cur].emplace_back(now, i);
        } else {
            now += A[i];
            g[cur].emplace_back(A[i], i);
            if (now == gsiz) {
                ++cur;
                now = 0;
            }
        }
    }

    std::vector<std::vector<i64>> ans;
    while (true) {
        debug(g);
        ans.push_back({});
        i64 take = g[0].front().first;
        for (int i = 0; i < K; ++i) {
            take = std::min(take, g[i].front().first);
        }
        ans.back().emplace_back(take);
        for (int i = 0; i < K; ++i) {
            ans.back().emplace_back(g[i].front().second);
            g[i].front().first -= take;
            if (g[i].front().first == 0) {
                g[i].pop_front();
            }
        }
        int bad = 0;
        for (int i = 0; i < K; ++i) {
            bad += g[i].empty();
        }
        assert(bad == 0 || bad == K);
        if (bad == K) {
            break;
        }
    }

    std::cout << int(ans.size()) << '\n';
    for (auto& v : ans) {
        std::cout << v[0] << ' ';
        for (int i = 1; i <= K; ++i) {
            std::cout << v[i] + 1 << " \n"[i == K];
        }
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51