Submission #859067

#	Time	Username	Problem	Language	Result	Execution time	Memory
859067		NaimSS	Gift (IZhO18_nicegift)	C++14	100 / 100	1514 ms	112500 KiB

nicegift

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define ff first 
#define ss second
using namespace std;
typedef long long ll;

const int N = 1e6 + 100;
ll a[N];
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;
	cin >> n >> k;
	ll sum=0;
	rep(i,0,n){
		cin >> a[i];
		sum += a[i];
	}
	if(sum%k != 0){
		cout << -1 << endl;
		return 0;
	}
	vector<pair<ll,vector<int>> > res;

	ll divi = sum/k;
	rep(i,0,n)if(a[i] > divi){
		cout << -1 << endl;
		return 0;
	}
	vector<vector<pair<ll,ll>>> nv;
	int pt=0;

	while(pt < n){
		ll need = divi;
		vector<pair<ll,ll>> here;
		while(need > 0){
			while(pt < n && a[pt]==0)pt++;
			assert(pt < n);
			ll put = min(a[pt], need);
			if(a[pt] > divi){
				cout << -1 << endl;
				return 0;
			}
			a[pt] -= put;
			need -= put;
			assert(put > 0 && need>=0 && a[pt] >= 0);
			here.pb({put , pt});
		}
		while(pt < n && a[pt]==0)pt++;
		nv.pb(here);
	}
	ll put = 0;
	while(divi > 0){
		ll mn = 1e18;
		for(auto &v : nv){
			mn = min(mn,v.back().ff);
		}
		divi -= mn;
		vector<int> here;
		for(auto &v : nv){
			here.pb(v.back().ss);
			v.back().ff -= mn;
			while(v.size() && v.back().ff == 0)v.pop_back();
		}
		assert(mn > 0);
		res.pb({mn, here});
	}
	cout << res.size() << endl;
	for(auto [X,v] : res){
		cout << X << " ";
		for(auto id : v)cout << id + 1<<" ";
		cout << endl;
	}
}

Compilation message (stderr)

nicegift.cpp: In function 'int32_t main()':
nicegift.cpp:70:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for(auto [X,v] : res){
      |           ^
nicegift.cpp:53:5: warning: unused variable 'put' [-Wunused-variable]
   53 |  ll put = 0;
      |     ^~~

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