Submission #872573

#	Time	Username	Problem	Language	Result	Execution time	Memory
872573		epicci23	Gift (IZhO18_nicegift)	C++17	0 / 100	449 ms	524288 KiB

nicegift

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

/*
 implement and debug smart
 DONT GET STUCK ON ONE APPROACH
 write smth on paper
 edge cases (n=1?)
 rewrite the problem
 simplify
 transform the problem into other problem
*/


void solve(){
  int n,k;
  cin >> n >> k;
  
  int ar[n+5];
  int sum=0;


  for(int i=1;i<=n;i++){
    cin >> ar[i];
    sum+=ar[i];
  }
 
  if(sum%k){
    cout << -1 << endl;
    return;
  }
  
  deque<int> cur;

  vector<deque<int>> ans;


  vector<array<int,2>> v;

  for(int i=1;i<=n;i++){
    v.pb({ar[i],i});
  }

  sort(all(v));

  for(int i=0;i<k;i++) cur.pb(v[i][1]);
  
  for(int i=0;i<n;i++){

    if(v[i][0]==0){
      cur.pop_front();
      continue;
    }

    if(sz(cur)<k){

      for(int j=min(i+sz(cur),n);j<min(n,i+k);j++) cur.pb(v[j][1]);

      if(sz(cur)<k){
        cout << -1 << endl;
        return;
      }

    }

    for(int j=0;j<v[i][0];j++) ans.pb(cur);
    int u = v[i][0];
    for(int j=i;j<i+k;j++) v[j][0]-=u;
    cur.pop_front();
  }
  


  cout << sz(ans) << endl;
  for(deque<int> x:ans){
    cout << 1 << " ";
    for(int u : x) cout << u << " ";
    cout << endl;
  }


}

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

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