Submission #50861

#	Time	Username	Problem	Language	Result	Execution time	Memory
50861		Nicksechko	Gift (IZhO18_nicegift)	C++14	100 / 100	1035 ms	95192 KiB

nicegift

#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MAXN = 1000100;

vector<vector<ll>> ans;
int n, k;
pair<ll, ll> a[MAXN];
ll sum;
ll mx;

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i)
		scanf("%lld", &a[i].first), sum += a[i].first, mx = max(mx, a[i].first), a[i].second = i + 1;
	sort(a, a + n);
	if (sum % k != 0 || mx > sum / k) {
		cout << -1 << "\n";
		return 0;
	}
	int lb = 0;
	int rb = n - 1;
	int len = k;
	ll rq = sum / k;
	while (rb - lb >= 0) {
		mx = a[rb].first;
		while (mx < rq && rb - lb + 1 > len) {
			if (a[lb].first == 0) {
				++lb;
				continue;
			}
			ll x = min(rq - mx, a[lb].first);
			vector<ll> vv;
			vv.push_back(x);
			for (int i = lb; i < lb + len; ++i)
				vv.push_back(a[i].second), a[i].first -= x;
			for (int i = rb + 1; i < n; ++i)
				vv.push_back(a[i].second), a[i].first -= x;
			ans.push_back(vv);
			rq -= x;
		}
		if (rb - lb + 1 == len) {
			vector<ll> vv;
			vv.push_back(a[n - 1].first);
			for (int i = lb; i < n; ++i)
				vv.push_back(a[i].second), a[i].first -= vv[0];
			ans.push_back(vv);
			break;
		}
		--rb;
		--len;
	}
	printf("%d\n", (int)ans.size());
	for (int i = 0; i < ans.size(); ++i) {
		for (ll j: ans[i])
			printf("%lld ", j);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); ++i) {
                  ~~^~~~~~~~~~~~
nicegift.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
nicegift.cpp:32:74: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i].first), sum += a[i].first, mx = max(mx, a[i].first), a[i].second = i + 1;
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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