Submission #65185

#	Time	Username	Problem	Language	Result	Execution time	Memory
65185		kingpig9	Gift (IZhO18_nicegift)	C++11	49 / 100	471 ms	23944 KiB

nicegift

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

void kill() {
	puts("-1");
	exit(0);
}

int N, K;
ll A[MAXN], suma;

namespace subtask3 {
	void go() {
		priority_queue<pll> pq;
		for (int i = 0; i < N; i++) {
			pq.push(pll(A[i], i));
		}

		vector<vector<ll>> ans;
		while (!pq.empty()) {
			vector<ll> vnew;
			for (int i = 0; i < K; i++) {
				if (pq.empty()) {
					kill();
				}
				ll ind = pq.top().se;
				pq.pop();
				vnew.push_back(ind);
			}
			ans.push_back(vnew);

			for (ll ind : vnew) {
				if (--A[ind]) {
					pq.push(pll(A[ind], ind));
				}
			}
		}

		printf("%lld\n", suma / K);
		for (vector<ll> v : ans) {
			assert(v.size() == K);
			printf("1");
			for (ll x : v) {
				printf(" %lld", x + 1);
			}
			puts("");
		}
	}
}

namespace subtask4 {
	void go() {
		ll g = __gcd(N, K);
		ll v = A[0] * g / K;
		ll nturns = N / g;
		printf("%lld\n", nturns);

		int ptr = 0;
		for (ll i = 0; i < nturns; i++) {
			printf("%lld", v);
			for (int j = 0; j < K; j++) {
				printf(" %d", ptr + 1);
				ptr = (ptr + 1) % N;
			}
			puts("");
		}
	}
}

int main() {
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < N; i++) {
		scanf("%lld", &A[i]);
		suma += A[i];
	}

	if (suma % K != 0) {
		kill();
	}

	if (suma <= 1e5) {
		subtask3::go();
	} else {
		subtask4::go();
	}
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from nicegift.cpp:1:
nicegift.cpp: In function 'void subtask3::go()':
nicegift.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    assert(v.size() == K);
           ~~~~~~~~~^~~~
nicegift.cpp: In function 'int main()':
nicegift.cpp:82: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:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~

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