Submission #1211806

#TimeUsernameProblemLanguageResultExecution timeMemory
1211806catch_me_if_you_canGift (IZhO18_nicegift)C++20
49 / 100
649 ms589824 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;

signed main()
{
	fast();
	int n, k; cin >> n >> k;
	vector<in> b(n+1); b[0] = {INF, 0};
	vector<int> a(n+1);
	int S = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> b[i][0]; b[i][1] = i;
		S+=b[i][0];
	}
	sort(b.rbegin(), b.rend());
	for(int i = 1; i <= n; i++)
		a[i] = b[i][0];
	vector<pair<int, vector<int>>> op;
	if((S%k) || (a[1] > (S/k)))
	{
		cout << "-1\n";
		return 0;
	}
	int g = n;
	int s = 1;
	while(true)
	{
		//Currently we want to achieve a[s] = S/k, previous ones are already S/k
		//reduce S to a[i]*k
		if(a[s] == (S/k))
		{
			s++;
			continue;
		}
		if(a[s] == 0)
		{
			s--;
			break;
		}
		vector<int> act;
		for(int i = 1; i < s; i++)
			act.pb(i);
		while(a[g] == 0)
			g--;
		int d = g;
		while(act.size() != k)
		{
			act.pb(d);
			d--;
		}
		int D = min(a[g], (S/k)-a[s]);
		op.pb({D, act});
		for(auto s: act)
		{
			a[s]-=D;
			S-=D;
		}
	}
	if(a[1])
	{
		vector<int> act;
		for(int i = 1; i <= k; i++)
			act.pb(i);
		op.pb({a[1], act});
	}
	cout << op.size() << "\n";
	for(auto [M, xooks]: op)
	{
		cout << M << " ";
		for(auto x: xooks)
			cout << b[x][1] << " ";
		cout << "\n";
	}
	return 0;
}	
#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...