제출 #1239927

#제출 시각아이디문제언어결과실행 시간메모리
1239927_callmelucianGift (IZhO18_nicegift)C++17
0 / 100
419 ms54128 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, k; cin >> n >> k;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    ll sum = accumulate(all(a), 0LL), lim = sum / k;
    if (sum % k || *max_element(all(a)) > lim) return cout << -1 << "\n", 0;

    vector<pl> events; ll cur = 0;
    for (int i = 1; i <= n; i++) {
        if (cur + a[i] > lim) {
            // place at [cur + 1..lim] of current row and [1..cur + a[i] - lim] of next row
            events.emplace_back(cur + 1, i);
            events.emplace_back(lim, -i);
            events.emplace_back(1, i);
            events.emplace_back(cur + a[i] - lim, -i);
            cur += a[i] - lim;
        }
        else {
            // place at [cur + 1..cur + a[i]] of current row
            events.emplace_back(cur + 1, i);
            events.emplace_back(cur + a[i], -i);
            cur += a[i];
        }
    }
    sort(all(events));

    set<int> active;
    ll last = 0;
    for (int i = 0; i < events.size();) {
        ll p = events[i].first;
        vector<int> toErase;

        for (; i < events.size() && events[i].first == p; i++) {
            int idx = events[i].second;
            if (idx > 0) active.insert(idx);
            else toErase.push_back(-idx);
        }
        if (toErase.empty()) continue;

        cout << p - last << " ";
        for (int u : active) cout << u << " ";
        cout << "\n";

        for (int u : toErase) active.erase(u);
        last = p;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...