Submission #1130693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130693		Gray	Gift (IZhO18_nicegift)	C++20	100 / 100	591 ms	106008 KiB

nicegift

#include <bits/stdc++.h>
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<pair<ll, ll>> a(n);
    ll sum=0;
    for (ll i=0; i<n; i++){
        cin >> a[i].ff; a[i].ss=i;
        sum+=a[i].ff;
    }
    sort(a.begin(), a.end());
    if (a.back().ff>sum-a.back().ff or sum%k){
        cout << -1 << ln; return;
    }
    vector<ll> divider;
    ll op_cnt = sum/k, cur=0;
    for (ll i=0; i<n; i++){
        cur+=a[i].ff;
        cur%=op_cnt;
        if (cur) divider.push_back(cur);
    }
    sort(divider.begin(), divider.end());
    divider.erase(unique(divider.begin(), divider.end()), divider.end());
    divider.push_back(op_cnt);
    vector<vector<ll>> opera(divider.size());
    cur=0; ll opi=0;
    for (ll i=0; i<n; i++){
        while (opi<(ll)divider.size() and divider[opi]<=min(op_cnt, cur+a[i].ff)){
            opera[opi].push_back(a[i].ss);
            opi++;
        }
        if (cur+a[i].ff<op_cnt){
            cur+=a[i].ff; continue;
        }else{
            a[i].ff=cur+a[i].ff-op_cnt;
            i--;
            cur=0; opi=0;
        }
    }
    cout << opera.size() << ln;
    for (ll i=0; i<(ll)opera.size(); i++){
        cout << divider[i]-(i?divider[i-1]:0) << " ";
        for (ll j=0; j<k; j++) cout << opera[i][j]+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: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51