Submission #1181426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181426		PieArmy	Gift (IZhO18_nicegift)	C++20	100 / 100	1049 ms	107216 KiB

nicegift

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

ll n,k;
ll arr[1000023];
ll sum=0,q;
int per[1000023];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		sum+=arr[i];
	}
	if(sum%k){
		cout<<-1;
		return 0;
	}
	q=sum/k;
	for(int i=1;i<=n;i++){
		if(arr[i]>q){
			cout<<-1;
			return 0;
		}
	}
	iota(per+1,per+n+1,1);
	sort(per+1,per+n+1,[&](const int &x,const int &y){
		return arr[x]<arr[y];
	});
	int r=n;
	vector<int>v;
	while(arr[per[r]]==q){
		v.pb(per[r]);
		r--;
		k--;
	}
	int l=1;
	vector<vector<ll>>ans;
	while(l<=r){
		ll x=min(arr[per[l]],q-arr[per[r]]);
		ans.pb({x});
		for(int i=l;i<l+k;i++){
			ans.back().pb(per[i]);
			arr[per[i]]-=x;
		}
		for(int y:v){
			ans.back().pb(y);
		}
		while(arr[per[l]]==0){
			l++;
		}
		q-=x;
		while(arr[per[r]]==q){
			v.pb(per[r]);
			r--;
			k--;
		}
	}
	ans.pb({arr[v.back()]});
	for(int x:v){
		ans.back().pb(x);
	}
	cout<<ans.size()<<endl;
	for(auto x:ans){
		for(auto y:x){
			cout<<y<<" ";
		}
		cout<<endl;
	}
}

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