Submission #39804

#	Time	Username	Problem	Language	Result	Execution time	Memory
39804		14kg	Gap (APIO16_gap)	C++11	30 / 100	2000 ms	169828 KiB

gap

#include "gap.h"
#include <set>
#define NUM_MAX 1000000000000000000
#define R_MAX 1152921504606846976
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)

using namespace std;
int n;
set<long long> S;
set<pair<long long,long long> > pass;

long long f1() {
	long long l = 0, r = NUM_MAX;
	long long t1, t2, res = 0;

	while (l <= r) {
		MinMax(l, r, &t1, &t2);
		if (t1 < 0) break;
		
		S.insert(l = t1), S.insert(r = t2);
		l++, r--;
		if (S.size() == n) break;
	}
	
	t1 = NUM_MAX;
	for (auto i : S) res = max2(res, i - t1), t1 = i;
	return res;
}
long long get_pass(long long x) {
	set<pair<long long, long long>>::iterator it = pass.upper_bound({ x,-1 });
	if (it == pass.end()) return -1;
	if (it->first == x) return it->second;
	return -1;
}
bool Can(long long len) {
	long long back_MAX = NUM_MAX;
	long long t1, t2;

	for (long long s = 0; s <= NUM_MAX; s += len) {
		t2 = get_pass(s);
		if (t2 > 0) { s = t2 - len;  continue; }

		MinMax(s, min2(NUM_MAX, s + len - 1), &t1, &t2);
		if (t1 < 0) { pass.insert({ s,s + len }); continue; }
		if (t1 - back_MAX >= len) return true;
		back_MAX = t2;
	} return false;
}
long long f2() {
	long long l = 1, r = R_MAX, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (Can(mid)) l = mid + 1;
		else r = mid - 1;
	} return l - 1;
}
long long findGap(int T, int _n) {
	n = _n;
	if (T == 1) return f1();
	else return f2();
}

Compilation message (stderr)

gap.cpp: In function 'long long int f1()':
gap.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (S.size() == n) break;
                ^

• Subtask 1: 30 / 30
• Subtask 2: 0 / 70