Submission #744286

#	Time	Username	Problem	Language	Result	Execution time	Memory
744286		b00norp	Gap (APIO16_gap)	C++14	46.81 / 100	80 ms	5788 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)
{
	if(T == 1)
	{	
		long long mn = 0, mx = 1e18;
		vector<long long> a(N);
		int l = 0, r = N - 1;
		while(l <= r)
		{
			MinMax(mn, mx, &mn, &mx);
			// cout << "mn = " << mn << ", mx = " << mx << "\n";
			a[l++] = mn;
			a[r--] = mx;
			mn += 1;
			mx -= 1;
		}
		long long diff = 0;
		for(int i = 1; i < N; i++)
		{
			diff = max(diff, a[i] - a[i - 1]);
		}
		return diff;
	}
	long long mn = 0, mx = 1e18;
	long long mid = (mn + mx) / 2;
	solve(mn, mid);
	solve(mid + 1, 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: 30 / 30
• Subtask 2: 16.8129163383 / 70