oj.uz

Submission #65181

# Submission time Handle Problem Language Result Execution time Memory
65181 2018-08-07T00:32:40 Z kingpig9 Gift (IZhO18_nicegift) C++11
26 / 100
 2000 ms 52148 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() {
		printf("%lld\n", suma / K);

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

		while (!pq.empty()) {
			vector<pll> vnew;
			printf("1");
			for (int i = 0; i < K; i++) {
				pll p = pq.top();
				pq.pop();
				if (--p.fi) {
					vnew.push_back(p);
				}
				printf(" %lld", p.se + 1);
			}
			puts("");

			for (pll p : vnew) {
				pq.push(p);
			}
		}
	}
}

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:72: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:75: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 2 ms 504 KB n=4
2 Correct 2 ms 504 KB n=3
3 Correct 3 ms 508 KB n=3
4 Correct 3 ms 508 KB n=4
5 Correct 3 ms 572 KB n=4
6 Correct 3 ms 632 KB n=2

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB n=4
2 Correct 2 ms 504 KB n=3
3 Correct 3 ms 508 KB n=3
4 Correct 3 ms 508 KB n=4
5 Correct 3 ms 572 KB n=4
6 Correct 3 ms 632 KB n=2
7 Correct 2 ms 680 KB n=5
8 Execution timed out 2051 ms 45636 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB n=4
2 Correct 2 ms 504 KB n=3
3 Correct 3 ms 508 KB n=3
4 Correct 3 ms 508 KB n=4
5 Correct 3 ms 572 KB n=4
6 Correct 3 ms 632 KB n=2
7 Correct 2 ms 680 KB n=5
8 Execution timed out 2051 ms 45636 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 45636 KB n=1000000
2 Correct 346 ms 45636 KB n=666666
3 Correct 155 ms 45636 KB n=400000
4 Correct 326 ms 51880 KB n=285714
5 Correct 14 ms 51880 KB n=20000
6 Correct 319 ms 52148 KB n=181818
7 Correct 9 ms 52148 KB n=10000
8 Correct 41 ms 52148 KB n=6666
9 Correct 5 ms 52148 KB n=4000
10 Correct 231 ms 52148 KB n=2857
11 Correct 6 ms 52148 KB n=2000

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB n=4
2 Correct 2 ms 504 KB n=3
3 Correct 3 ms 508 KB n=3
4 Correct 3 ms 508 KB n=4
5 Correct 3 ms 572 KB n=4
6 Correct 3 ms 632 KB n=2
7 Correct 2 ms 680 KB n=5
8 Execution timed out 2051 ms 45636 KB Time limit exceeded
9 Halted 0 ms 0 KB -