Submission #1112715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112715		noyancanturk	Gift (IZhO18_nicegift)	C++17	100 / 100	911 ms	113236 KiB

nicegift

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
using pii=pair<int,int>;
const int lim=1e5+100;

struct op{
  int val;
  vector<int>inds;
};

signed main(){
  int n,k;
  cin>>n>>k;
  int a[n],sm=0;
  for(int i=0;i<n;i++)cin>>a[i],sm+=a[i];
  int p[n];
  iota(p,p+n,0);
  sort(p,p+n,[&](int i,int j)->bool {
    return a[i]>a[j];
  });
  if(sm%k){
    cout<<-1;
    return 0;
  }
  sm/=k;
  if(sm<a[p[0]]){
    cout<<-1;
    return 0;
  }
  vector<op>ops;
  int left=n;
  while(left&&a[p[0]]!=a[p[left-1]]){
    op todo;
    int last=0;
    for(;last<n;last++){
      if(a[p[last]]==sm){
        todo.inds.pb(p[last]);
      }else break;
    }
    todo.val=min(a[p[left-1]],sm-a[p[last]]);
    for(int i=left-1;todo.inds.size()<k;i--){
      todo.inds.pb(p[i]);
    }
    sm-=todo.val;
    for(int i:todo.inds){
      a[i]-=todo.val;
    }
    ops.pb(todo);
    while(left&&a[p[left-1]]==0)left--;
  }
  if(left){
    int z=left/gcd(left,k);
    int val=sm/z;
    int i=0;
    for(int t=0;t<z;t++){
      op todo;
      todo.val=val;
      for(int j=0;j<k;j++,(i=((i+1)%left))){
        todo.inds.pb(p[i]);
      }
      ops.pb(todo);
    }
  }
  cout<<ops.size()<<'\n';
  for(op&pp:ops){
    cout<<pp.val<<' ';
    for(int i:pp.inds){
      cout<<i+1<<' ';
    }
    cout<<'\n';
  }
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:43:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |     for(int i=left-1;todo.inds.size()<k;i--){
      |                      ~~~~~~~~~~~~~~~~^~

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