Submission #394436

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394436	2021-04-26T16:23:08 Z	danielcm585	Gap (APIO16_gap)	C++14	100 / 100	72 ms	3252 KB

gap

#include "gap.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MX = 1e18;
ll x, y;
vector<ll> p;

void query(ll l, ll r) {
	MinMax(l,r,&x,&y);
	if (x != -1) p.push_back(x);
	if (y != -1) p.push_back(y);
}

ll findGap(int T, int N) {
	ll l = 0, r = MX;
	if (T == 1) {
		for (int i = 1; i <= (N+1)/2 && l <= r; i++) {
			query(l,r);
			l = x+1, r = y-1;
		}
	}
	else {
		query(l,r);
		l = x+1, r = y-1;
		for (int i = N-1; i > 0; i--) {
			ll q = l+(r-l)/i;
			query(l,q);
			l = q+1;
		}
	}
	sort(p.begin(),p.end());
	p.resize(unique(p.begin(),p.end())-p.begin());
	ll ans = 0;
	for (int i = 1; i < p.size(); i++) {
		ans = max(ans,p[i]-p[i-1]);
	}
	return ans;
}

Compilation message

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 1; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	328 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	0 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	1 ms	200 KB	Output is correct
6	Correct	1 ms	200 KB	Output is correct
7	Correct	1 ms	200 KB	Output is correct
8	Correct	1 ms	200 KB	Output is correct
9	Correct	1 ms	200 KB	Output is correct
10	Correct	1 ms	200 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	2 ms	328 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	13 ms	828 KB	Output is correct
17	Correct	14 ms	840 KB	Output is correct
18	Correct	13 ms	844 KB	Output is correct
19	Correct	14 ms	840 KB	Output is correct
20	Correct	10 ms	840 KB	Output is correct
21	Correct	53 ms	2140 KB	Output is correct
22	Correct	51 ms	2232 KB	Output is correct
23	Correct	51 ms	2232 KB	Output is correct
24	Correct	50 ms	2196 KB	Output is correct
25	Correct	52 ms	2232 KB	Output is correct
26	Correct	62 ms	2232 KB	Output is correct
27	Correct	52 ms	2228 KB	Output is correct
28	Correct	50 ms	2200 KB	Output is correct
29	Correct	53 ms	2232 KB	Output is correct
30	Correct	41 ms	2248 KB	Output is correct
31	Correct	1 ms	200 KB	Output is correct
32	Correct	1 ms	200 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	1 ms	200 KB	Output is correct
6	Correct	1 ms	200 KB	Output is correct
7	Correct	1 ms	200 KB	Output is correct
8	Correct	1 ms	200 KB	Output is correct
9	Correct	1 ms	200 KB	Output is correct
10	Correct	1 ms	200 KB	Output is correct
11	Correct	2 ms	328 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	16 ms	840 KB	Output is correct
17	Correct	17 ms	856 KB	Output is correct
18	Correct	16 ms	868 KB	Output is correct
19	Correct	19 ms	844 KB	Output is correct
20	Correct	10 ms	456 KB	Output is correct
21	Correct	66 ms	2200 KB	Output is correct
22	Correct	68 ms	2264 KB	Output is correct
23	Correct	67 ms	2172 KB	Output is correct
24	Correct	66 ms	2196 KB	Output is correct
25	Correct	68 ms	3252 KB	Output is correct
26	Correct	68 ms	2260 KB	Output is correct
27	Correct	70 ms	2148 KB	Output is correct
28	Correct	72 ms	2232 KB	Output is correct
29	Correct	67 ms	2216 KB	Output is correct
30	Correct	35 ms	1420 KB	Output is correct
31	Correct	1 ms	200 KB	Output is correct
32	Correct	1 ms	200 KB	Output is correct