Submission #93296

#TimeUsernameProblemLanguageResultExecution timeMemory
93296AbelyanGift (IZhO18_nicegift)C++17
30 / 100
443 ms204100 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORR(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTR(i,a,b) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define fr first
#define sc second

const int N=1e6+6;
ll a[N],indcomp[N];
vector<pair<ll,int> > comp[N];
vector<int> ans[N];
int main(){
    ios_base::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    ll sum=0;
    ll mx=0;
    FOR(i,n){
        cin>>a[i];
        sum+=a[i];
        mx=max(mx,a[i]);
    }
    if (sum%k!=0 || sum/k<mx){
        cout<<-1<<endl;
        return 0;
    }
    ll tv=0,sahm=sum/k,cnt=0;
    FOR(i,n){
        if (!a[i])continue;
        if (tv+a[i]>=sahm){
            comp[cnt].push_back({sahm-tv,i+1});
            a[i]-=sahm-tv;
            cnt++;
            tv=0;
            i--;
            continue;
        }
        comp[cnt].push_back({a[i],i+1});
        tv+=a[i];
    }
    int hert=0;
    while(sum){
        //cout<<sum<<endl;
        ll mn=INT_MAX;
        FOR(i,k){
            mn=min(mn,comp[i][indcomp[i]].fr);
        }
        ans[hert].push_back(mn);
        FOR(i,k){
            comp[i][indcomp[i]].fr-=mn;
            ans[hert].push_back(comp[i][indcomp[i]].sc);
            if (comp[i][indcomp[i]].fr==0)
                indcomp[i]++;
        }
        hert++;
        sum-=(k*mn);
    }
    cout<<hert<<endl;
    FOR(i,hert){
        //cout<<ans[i].size()<<" ";
        trav(tt,ans[i])cout<<tt<<" ";
        cout<<endl;
    }
    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...