Submission #744275

#	Time	Username	Problem	Language	Result	Execution time	Memory
744275		b00norp	Gap (APIO16_gap)	C++14	12.89 / 100	80 ms	5832 KiB

gap

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

set<long long> a;

void solve(long long min_val, long long max_val)
{
	if(min_val > max_val)
	{
		return;
	}
	long long mn, mx;
	MinMax(min_val, max_val, &mn, &mx);
	if(mn == -1)
	{
		return;
	}
	a.insert(mn);
	a.insert(mx);
	if(mn == mx)
	{
		return;
	}
	min_val = mn + 1;
	max_val = mx - 1;
	long long mid = (min_val + max_val) / 2;
	solve(min_val, mid);
	solve(mid + 1, max_val);
}

long long findGap(int T, int N)
{
	long long mn = 0, mx = 1e18;
	solve(mn, mx);
	long long diff = 0;
	long long prev = *(a.begin());
	for(auto i: a)
	{
		diff = max(diff, i - prev);
		prev = i;
	}
	return diff;
}

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