Submission #1170276

#TimeUsernameProblemLanguageResultExecution timeMemory
1170276mnbvcxz123Gift (IZhO18_nicegift)C++20
100 / 100
809 ms426332 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 500003
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
 
ll n, t, m, jog, mx, sum, cnt = 1, a[N * 10];
vector <vector<ll>> ans;
queue <pair<ll,int>> v[N];
 
int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n; i++) {
		cin >> a[i];
		sum += a[i];
		mx = max(mx,a[i]);
	}
	if(sum % m != 0 || mx > sum / m) {
		cout << "-1\n";
		return 0;
	}
	int inx = 1;
	for(int i = 1; i <= n; i++) {
		if(jog == sum/m) {
			jog = 0;
			inx++;
		}
		if(jog + a[i] <= sum/m) {
			jog += a[i];
			v[inx].push({a[i],i});
			continue;
		}
		v[inx].push({sum/m - jog,i});
		a[i] -= (sum/m - jog);
		jog = a[i];
		inx++;
		v[inx].push({jog,i});
	}
	while(!v[1].empty()) {
		ll mn = LLONG_MAX;
		vector <ll> jogap;
		for(int i = 1; i <= inx; i++) {
			mn = min(mn,v[i].front().ff);
		}
		jogap.pb(mn);
		for(int i = 1; i <= inx; i++) {
			jogap.pb(v[i].front().ss);
			v[i].front().ff  -= mn;
			if(!v[i].front().ff) v[i].pop();
		}
		ans.pb(jogap);
	}
	cout << sz(ans) << '\n';
	for(int i = 0; i < sz(ans); i++) {
		for(auto j : ans[i]) {
			cout << j << " ";
		}
		cout << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...