Submission #139026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139026	2019-07-31T07:53:18 Z	sheyasutaka	Gap (APIO16_gap)	C	100 / 100	126 ms	2680 KB

gap

#include "gap.h"

long long findGap(int T, int N) {
	long long a[N * 2], ln = 0;
	long long l = 0, r = 1000000000000000000LL;
	if (T == 1) {
		int i = 0, j = N - 1;
		while (i <= j) {
			MinMax(l, r, &a[i], &a[j]);
			l = a[i] + 1;
			r = a[j] - 1;
			i++;
			j--;
		}
		ln = N;
	} else {
		MinMax(l, r, &l, &r);
		long long len = (r - l - 1) / (N - 1);
		long long ad = (r - l - 1) % (N - 1);


		a[ln++] = l;
		long long x, y;
		l++;
		for (int i = 0; i < N - 1; i++) {
			long long lx = len + ((i < ad) ? 1 : 0);
			if (lx == 0) continue;
			MinMax(l, l + lx - 1, &x, &y);
			l += lx;

			if (x >= 0) {
				a[ln++] = x;
				a[ln++] = y;
			}
		}
		a[ln++] = r;
	}

	long long result = 0;
	for (int i = 1; i < ln; i++) {
		long long maybe = a[i] - a[i - 1];
		if (maybe > result) result = maybe;
	}
	return result;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	424 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	15 ms	760 KB	Output is correct
17	Correct	15 ms	764 KB	Output is correct
18	Correct	15 ms	760 KB	Output is correct
19	Correct	15 ms	732 KB	Output is correct
20	Correct	12 ms	632 KB	Output is correct
21	Correct	57 ms	2040 KB	Output is correct
22	Correct	57 ms	1912 KB	Output is correct
23	Correct	59 ms	1912 KB	Output is correct
24	Correct	57 ms	1912 KB	Output is correct
25	Correct	48 ms	1912 KB	Output is correct
26	Correct	57 ms	1912 KB	Output is correct
27	Correct	58 ms	1884 KB	Output is correct
28	Correct	58 ms	1912 KB	Output is correct
29	Correct	56 ms	1912 KB	Output is correct
30	Correct	42 ms	1912 KB	Output is correct
31	Correct	2 ms	256 KB	Output is correct
32	Correct	2 ms	252 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	20 ms	888 KB	Output is correct
17	Correct	20 ms	888 KB	Output is correct
18	Correct	20 ms	888 KB	Output is correct
19	Correct	20 ms	1016 KB	Output is correct
20	Correct	9 ms	504 KB	Output is correct
21	Correct	80 ms	2172 KB	Output is correct
22	Correct	82 ms	2144 KB	Output is correct
23	Correct	79 ms	2296 KB	Output is correct
24	Correct	78 ms	2268 KB	Output is correct
25	Correct	72 ms	2680 KB	Output is correct
26	Correct	81 ms	2168 KB	Output is correct
27	Correct	78 ms	2196 KB	Output is correct
28	Correct	80 ms	2288 KB	Output is correct
29	Correct	126 ms	2168 KB	Output is correct
30	Correct	39 ms	1272 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct