제출 #1129546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129546		Tsagana	Gift (IZhO18_nicegift)	C++17	100 / 100	859 ms	83448 KiB

nicegift

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

void solve () {
	int n, k; cin >> n >> k;
	pq<pair<int, int>> q;
	vector<int> a(n+1);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
		q.push({a[i], i});
	}

	if (sum % k) {cout << "-1"; return ;}
	if (q.top().F > sum / k) {cout << "-1"; return ;}

	vector<vector<int>> ans;
	while (sum) {
		vector<int> v;
		int s = INT_MAX;
		for (int i = 1; i <= k; i++) {
			v.pb(q.top().S);
			s = q.top().F;
			q.pop();
		}
		if (!q.empty()) s = min(s, (sum / k) - q.top().F);
		sum -= k * s;

		vector<int> t; t.pb(s);
		for (auto i: v) {
			t.pb(i);
			a[i] -= s;
			if (a[i]) q.push({a[i], i});
		}
		ans.pb(t);
	}

	cout << ans.size() << '\n';
	for (auto v: ans) {
		for (auto i: v) cout << i << ' ';
		cout << '\n';
	}
}
signed main() {IOS solve(); return 0;}

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