Submission #1128828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128828		Gray	Gift (IZhO18_nicegift)	C++20	7 / 100	656 ms	101048 KiB

nicegift

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
#include <functional>
#include <iomanip>
#include <queue>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;


void solve(){
    ll n, k; cin >> n >> k;
    vector<ll> a(n); ll sum=0;
    set<pair<ll, ll>> st;
    ll mx=0;
    for (ll i=0; i<n; i++){
        cin >> a[i]; sum+=a[i];
        mx=max(mx, a[i]);
        st.insert({a[i], i});
    }
    if (sum%k or sum-mx<mx) {cout << -1 << ln; return;}
    vector<pair<ll, vector<ll>>> op;
    while (!st.empty()){
        op.push_back({0, vector<ll>()});
        // assert((ll)st.size()>=k);
        for (ll j=0; j<k and !st.empty(); j++){
            op.back().ss.push_back((*st.rbegin()).ss);
            st.erase(*st.rbegin());
        }
        op.back().ff=a[op.back().ss.back()];
        for (auto i:op.back().ss){
            a[i]-=op.back().ff;
            // assert(a[i]>=0);
            if (a[i]>0){
                st.insert({a[i], i});
            }
        }
    }
    for (auto &ch:op){
        if ((ll)ch.ss.size()!=k){
            cout << -1 << ln; return;
        }
    }
    cout << op.size() << ln;
    reverse(op.begin(), op.end());
    for (auto &ch:op){
        cout << ch.ff << " ";
        for (auto ich:ch.ss) cout << ich+1 << " ";
        cout << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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