Submission #1314986

#TimeUsernameProblemLanguageResultExecution timeMemory
1314986aren_danceGift (IZhO18_nicegift)C++20
0 / 100
2097 ms39620 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+1;
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n+1);
    vector<priority_queue<pair<ll,int>>> mas;ll dt=0ll;
    vector<pair<ll,vector<int>>> answ;
    ll sum=0ll;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%k!=0){
        cout<<-1<<'\n';
        return 0;
    }
    sum/=k;
    for(int i=1;i<=n;++i){
        if(a[i]>sum){
            cout<<-1<<'\n';
            return 0;
        }
    }
    priority_queue<pair<ll,int>> res;
    for(int i=1;i<=n;++i){
        if((dt+a[i])==sum){
            res.push({a[i],i});
            mas.push_back(res);
            dt=0;
            while(!res.empty()){
                res.pop();
            }
        }
        else if(dt+a[i]>sum){
            res.push({sum-dt,i});
            mas.push_back(res);
            while(!res.empty()){
                res.pop();
            }
            res.push({a[i]-sum+dt,i});
            dt=a[i]-sum+dt;
        }
        else{
            res.push({a[i],i});
            dt+=a[i];
        }
    }
    while(!mas[0].empty()){
        ll mn=1e18;
        for(auto i:mas){
            ll g=i.top().first;
            mn=min(mn,g);
        }
        answ.push_back({mn,{}});
        for(int i=0;i<int(mas.size());++i){
            pair<ll,int> g=mas[i].top();
            mas[i].pop();
            mas[i].push({g.first-mn,g.second});
            answ.back().second.push_back(mas[i].top().second);
            if(mas[i].top().first==0){
                mas[i].pop();
            }
        }
    }
    cout<<answ.size()<<'\n';
    for(auto i:answ){
        cout<<i.first<<" ";
        for(auto j:i.second){
            cout<<j<<" ";
        }
        cout<<'\n';
    }
    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...