제출 #1211812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211812		catch_me_if_you_can	Gift (IZhO18_nicegift)	C++20	100 / 100	395 ms	173972 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 = 1e6+5;
const int INF = 1e17;
const int LMX = 3e6+4;

int a[MX];
in b[MX];

pair<int, vector<int>> op[LMX];

signed main()
{
	fast();
	int n, k; cin >> n >> k;
	b[0] = {INF, 0};
	int S = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> b[i][0]; b[i][1] = i;
		S+=b[i][0];
	}
	sort(b+1, b+n+1);
	reverse(b+1, b+n+1);
	for(int i = 1; i <= n; i++)
		a[i] = b[i][0];
	if((S%k) || (a[1] > (S/k)))
	{
		cout << "-1\n";
		return 0;
	}
	int CUR = 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;
		}
		while(a[g] == 0)
			g--;
		int D = min(a[g], (S/k)-a[s]);
		for(int i = 1; i < s; i++)
		{
			op[CUR].second.pb(i);
			a[i]-=D;
		}
		int d = g;
		while(op[CUR].second.size() != k)
		{
			op[CUR].second.pb(d); a[d]-=D;
			d--;
		}
		op[CUR].first = D;
		S-=(D*k);
		CUR++;
	}
	if(a[1])
	{
		for(int i = 1; i <= k; i++)
			op[CUR].second.pb(i);
		op[CUR].first = a[1];
		CUR++;
	}
	cout << CUR << "\n";
	for(int i = 0; i < CUR; i++)
	{
		cout << op[i].first << " ";
		for(auto x: op[i].second)
			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: 51 / 51