Submission #341540

#	Time	Username	Problem	Language	Result	Execution time	Memory
341540		ivan_tudor	Gift (IZhO18_nicegift)	C++14	0 / 100	119 ms	34064 KiB

nicegift

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
priority_queue <pair<long long, int>> pq;
long long v[N];
vector<vector<int>> ans;
vector<long long> ansx;
int main()
{
  freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, k;
  cin>>n>>k;
  long long sum = 0, mx = 0;
  for(int i=1;i<=n;i++){
    cin>>v[i];
    pq.push({v[i], i});
    sum+=v[i];
    mx = max(mx, v[i]);
  }
  if(sum%k!=0 || sum/k < mx ){
    cout<<"-1\n";
    return 0;
  }
  long long op = sum / k;
  while(pq.size()){
    vector<int> aux;
    for(int i = 1 ;i <=k;i++){
      aux.push_back(pq.top().second);
      pq.pop();
    }
    long long mn = v[aux[aux.size() - 1]];
    long long nxt = 0;
    if(pq.size())
      nxt = pq.top().first;
    long long newX = min(mn, op - nxt);
    op -= newX;
    ansx.push_back(newX);
    ans.push_back(aux);
    for(auto x : aux){
      v[x] -= newX;
      if(v[x])
        pq.push({v[x], x});
    }
  }
  cout<<ans.size()<<"\n";
  for(int i= 0; i<ans.size();i++){
    cout<<ansx[i]<<" ";
    for(auto x : ans[i])
      cout<<x<<" ";
    cout<<"\n";
  }
  return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i= 0; i<ans.size();i++){
      |                 ~^~~~~~~~~~~
nicegift.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   10 |   freopen(".in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~

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