Submission #926698

#	Time	Username	Problem	Language	Result	Execution time	Memory
926698		shenfe1	Gift (IZhO18_nicegift)	C++17	100 / 100	608 ms	121896 KiB

nicegift

#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define ll long long
#define maksim gay
#define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound

const int MAX=2e6+10;
const int inf=1e10;
const int N=2e5;

int n,k;
int sum;
int a[MAX];

void solve(){
  cin>>n>>k;
  priority_queue<pii> q;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    sum+=a[i];
    q.push({a[i],i});
  }
  if(sum%k||q.top().F>sum/k){
    cout<<-1;
    return;
  }
  vector<vector<pii>> res;
  while(!q.empty()){
    vector<pii> v;
    for(int i=1;i<=k;i++){
      v.pb(q.top());
      q.pop();
    }
    int x=v.back().F;
    if(!q.empty())x=min(x,sum/k-q.top().F);
    sum-=k*x;
    v.pb({x,x});
    for(int i=0;i<k;i++){
      if(v[i].F!=x){
        v[i].F-=x;
        q.push(v[i]);
      }
    }
    res.pb(v);
  }
  reverse(all(res));
  cout<<sz(res)<<"\n";
  for(auto x:res){
    cout<<x.back().S<<" ";
    for(int i=0;i<k;i++)cout<<x[i].S<<" ";
    cout<<"\n";
  }
}


main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

nicegift.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main(){
      | ^~~~

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