Submission #1211806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211806		catch_me_if_you_can	Gift (IZhO18_nicegift)	C++20	49 / 100	649 ms	589824 KiB

nicegift

#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;
}	

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