oj.uz

Submission #65184

# Submission time Handle Problem Language Result Execution time Memory
65184 2018-08-07T00:52:58 Z kingpig9 Gift (IZhO18_nicegift) C++11
19 / 100
 418 ms 21844 KB 
#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();

				if (--A[ind]) {
					vnew.push_back(ind);
				}
			}
			ans.push_back(vnew);

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

		printf("%lld\n", suma / K);
		for (vector<ll> v : ans) {
			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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 272 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 272 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 272 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 21844 KB n=1000000
2 Correct 268 ms 21844 KB n=666666
3 Correct 150 ms 21844 KB n=400000
4 Correct 388 ms 21844 KB n=285714
5 Correct 12 ms 21844 KB n=20000
6 Correct 285 ms 21844 KB n=181818
7 Correct 10 ms 21844 KB n=10000
8 Correct 45 ms 21844 KB n=6666
9 Correct 4 ms 21844 KB n=4000
10 Correct 237 ms 21844 KB n=2857
11 Correct 4 ms 21844 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 272 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -