oj.uz

Submission #65185

# Submission time Handle Problem Language Result Execution time Memory
65185 2018-08-07T00:56:06 Z kingpig9 Gift (IZhO18_nicegift) C++11
49 / 100
 471 ms 23944 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();
				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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n=4
2 Correct 3 ms 376 KB n=3
3 Correct 2 ms 444 KB n=3
4 Correct 2 ms 500 KB n=4
5 Correct 3 ms 556 KB n=4
6 Correct 3 ms 564 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n=4
2 Correct 3 ms 376 KB n=3
3 Correct 2 ms 444 KB n=3
4 Correct 2 ms 500 KB n=4
5 Correct 3 ms 556 KB n=4
6 Correct 3 ms 564 KB n=2
7 Correct 2 ms 644 KB n=5
8 Correct 8 ms 1292 KB n=8
9 Correct 12 ms 1608 KB n=14
10 Correct 9 ms 1608 KB n=11
11 Correct 55 ms 5432 KB n=50000
12 Correct 55 ms 5576 KB n=50000
13 Correct 43 ms 5576 KB n=10
14 Correct 57 ms 5576 KB n=685
15 Correct 43 ms 5576 KB n=623
16 Correct 23 ms 5576 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n=4
2 Correct 3 ms 376 KB n=3
3 Correct 2 ms 444 KB n=3
4 Correct 2 ms 500 KB n=4
5 Correct 3 ms 556 KB n=4
6 Correct 3 ms 564 KB n=2
7 Correct 2 ms 644 KB n=5
8 Correct 8 ms 1292 KB n=8
9 Correct 12 ms 1608 KB n=14
10 Correct 9 ms 1608 KB n=11
11 Correct 55 ms 5432 KB n=50000
12 Correct 55 ms 5576 KB n=50000
13 Correct 43 ms 5576 KB n=10
14 Correct 57 ms 5576 KB n=685
15 Correct 43 ms 5576 KB n=623
16 Correct 23 ms 5576 KB n=973
17 Correct 38 ms 5576 KB n=989
18 Correct 18 ms 5576 KB n=563
19 Correct 27 ms 5576 KB n=592
20 Correct 25 ms 5576 KB n=938
21 Correct 24 ms 5576 KB n=747
22 Correct 24 ms 5576 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 23944 KB n=1000000
2 Correct 262 ms 23944 KB n=666666
3 Correct 167 ms 23944 KB n=400000
4 Correct 471 ms 23944 KB n=285714
5 Correct 12 ms 23944 KB n=20000
6 Correct 314 ms 23944 KB n=181818
7 Correct 9 ms 23944 KB n=10000
8 Correct 37 ms 23944 KB n=6666
9 Correct 4 ms 23944 KB n=4000
10 Correct 226 ms 23944 KB n=2857
11 Correct 5 ms 23944 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n=4
2 Correct 3 ms 376 KB n=3
3 Correct 2 ms 444 KB n=3
4 Correct 2 ms 500 KB n=4
5 Correct 3 ms 556 KB n=4
6 Correct 3 ms 564 KB n=2
7 Correct 2 ms 644 KB n=5
8 Correct 8 ms 1292 KB n=8
9 Correct 12 ms 1608 KB n=14
10 Correct 9 ms 1608 KB n=11
11 Correct 55 ms 5432 KB n=50000
12 Correct 55 ms 5576 KB n=50000
13 Correct 43 ms 5576 KB n=10
14 Correct 57 ms 5576 KB n=685
15 Correct 43 ms 5576 KB n=623
16 Correct 23 ms 5576 KB n=973
17 Correct 38 ms 5576 KB n=989
18 Correct 18 ms 5576 KB n=563
19 Correct 27 ms 5576 KB n=592
20 Correct 25 ms 5576 KB n=938
21 Correct 24 ms 5576 KB n=747
22 Correct 24 ms 5576 KB n=991
23 Correct 471 ms 23944 KB n=1000000
24 Correct 262 ms 23944 KB n=666666
25 Correct 167 ms 23944 KB n=400000
26 Correct 471 ms 23944 KB n=285714
27 Correct 12 ms 23944 KB n=20000
28 Correct 314 ms 23944 KB n=181818
29 Correct 9 ms 23944 KB n=10000
30 Correct 37 ms 23944 KB n=6666
31 Correct 4 ms 23944 KB n=4000
32 Correct 226 ms 23944 KB n=2857
33 Correct 5 ms 23944 KB n=2000
34 Incorrect 15 ms 23944 KB Taken too much stones from the heap
35 Halted 0 ms 0 KB -