Submission #106925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106925	2019-04-21T06:07:47 Z	tjd229	Gap (APIO16_gap)	C++14	70 / 100	84 ms	4432 KB

gap

#include "gap.h"
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
long long findGap(int T, int N)
{
	if (!N) return 0;
	vector<ll> a;
	ll res = 0;
	if (--T) {
		ll mn, mx,bnd;
		MinMax(0,1e18,&mn,&bnd);
		ll d = (bnd - mn)/(N-1);
		a.push_back(mn); a.push_back(bnd);
		ll l = mn, r = mn + d;
		res = d;
		for (;l< bnd;l+=d+1,r+=d+1) {
			MinMax(l, r, &mn, &mx);
			if (mn != -1) a.push_back(mn);
			if (mx != -1) a.push_back(mx);
		}
	}
	else {
		ll mn = -1, mx = 1e18+1;
		for (int i = N; i > 0; i -= 2) {
			MinMax(mn + 1, mx - 1,&mn,&mx);
			a.push_back(mn); a.push_back(mx);
		}
	}
	sort(a.begin(), a.end());
	for (int i = 1; i < a.size(); ++i) {
		ll d = a[i] - a[i - 1];
		if (res < d) res = d;
	}
	return res;
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); ++i) {
                  ~~^~~~~~~~~~

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	256 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	15 ms	1280 KB	Output is correct
17	Correct	17 ms	1280 KB	Output is correct
18	Correct	16 ms	1280 KB	Output is correct
19	Correct	19 ms	1280 KB	Output is correct
20	Correct	13 ms	896 KB	Output is correct
21	Correct	57 ms	3952 KB	Output is correct
22	Correct	73 ms	4080 KB	Output is correct
23	Correct	54 ms	4180 KB	Output is correct
24	Correct	53 ms	3952 KB	Output is correct
25	Correct	71 ms	3312 KB	Output is correct
26	Correct	54 ms	4080 KB	Output is correct
27	Correct	54 ms	4080 KB	Output is correct
28	Correct	57 ms	4052 KB	Output is correct
29	Correct	67 ms	4080 KB	Output is correct
30	Correct	42 ms	2928 KB	Output is correct
31	Incorrect	2 ms	384 KB	Output isn't correct
32	Correct	2 ms	256 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	0 ms	380 KB	Output is correct
13	Correct	4 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	24 ms	1272 KB	Output is correct
17	Correct	25 ms	1272 KB	Output is correct
18	Correct	19 ms	1244 KB	Output is correct
19	Correct	21 ms	1280 KB	Output is correct
20	Correct	11 ms	640 KB	Output is correct
21	Correct	77 ms	4080 KB	Output is correct
22	Correct	84 ms	4080 KB	Output is correct
23	Correct	75 ms	4080 KB	Output is correct
24	Correct	80 ms	3952 KB	Output is correct
25	Correct	67 ms	4432 KB	Output is correct
26	Correct	81 ms	4108 KB	Output is correct
27	Correct	71 ms	4084 KB	Output is correct
28	Correct	69 ms	4080 KB	Output is correct
29	Correct	71 ms	4080 KB	Output is correct
30	Correct	34 ms	2040 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct