| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 169399 | RafaelSus | Gift (IZhO18_nicegift) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const ll inf=1e18+18ll;
#define pb push_back
ll n,k;
ll a[N];
/*
void build(int v,int tl,int tr){
if(tl==tr)t[v]=a[tl],return;
int tm=(tl+tr)/2;
build(v+v,tl,tm);
build(v+v+1,tm+1,tr);
t[v]=min(t[v+v],t[v+v+1]);
}
void pushdown(int v){
if(lazy[v]==0)return;
t[v+v]-=lazy[v];
t[v+v+1]-=lazy[v];
lazy[v+v]+=lazy[v];
lazy[v+v+1]+=lazy[v];
lazy[v]=0;
}
void update(int v,int tl,int tr,int l,int r,ll d){
if(l>r)return;
if(tl>=l&&tr<=r){
lazy[v]+=d;
t[v]-=d;
return;
}
pushdown(v);
int tm=(tl+tr)/2;
if(l<=tm)update(v+v,tl,tm,l,r,d);
if(r>tm)update(v+v+1,tm+1,tr,l,r,d);
t[v]=min(t[v+v],t[v+v+1]);
}
ll query(int v,int tl,int tr,int l,int r){
if(tl>=l&&tr<=r)return t[v];
ll res=inf;
int tm=(tl+tr)/2;
pushdown(v);
if(l<=tm)res=min(res,query(v+v,tl,tm,l,r));
if(r>tm)res=min(res,query(v+v+1,tm+1,tr,l,r));
return res;
}*/
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll S=0ll;
cin>>n>>k;
priority_queue<pair<ll,int>> q;
for(int i=0;i<n;i++){
cin>>a[i];
q.push({a[i],i});
S+=a[i];
}
if(S%k||q.top().first>S/k){cout<<"-1\n";return 0;}
S/=k;
vector<vector<int>> answ;
ll cnt=0ll;
while(!q.empty()){
pair<int,int>tmp[k];
//if(q.size()<k){cout<<"-1\n";return 0;}
for(int i=0;i<k;i++){
tmp[i]=q.top();
q.pop();
}
vector<int> an;
ll mx=q.size()?q.top.first:0ll;
ll x=min(tmp[k-1].first,S-mx);
an.push_back(x);
for(int i=0;i<k;i++){
tmp[i].first-=x;
if(tmp[i].first!=0)q.push(tmp[i]);
an.push_back(tmp[i].second+1);
}
cnt+=(ll)an.size();
//if(cnt>=3*1e6){cout<<"-1";return 0;}
answ.push_back(an);
}
cout<<answ.size()<<'\n';
for(int i=0;i<answ.size();i++){
for(int j=0;j<answ[i].size();j++){
cout<<answ[i][j]<<' ';
}
cout<<'\n';
}
}