Submission #1239929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239929		_callmelucian	Gift (IZhO18_nicegift)	C++17	100 / 100	606 ms	129520 KiB

nicegift

#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())

vector<int> toVec (set<int> s) {
    vector<int> vec;
    for (int u : s) vec.push_back(u);
    return vec;
}

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

    vector<pair<ll,vector<int>>> opr;
    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;

        opr.emplace_back(p - last, toVec(active));
        for (int u : toErase) active.erase(u);
        last = p;
    }

    cout << opr.size() << "\n";
    for (auto [a, vec] : opr) {
        cout << a << " ";
        for (int u : vec) cout << u << " ";
        cout << "\n";
    }

    return 0;
}

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