Submission #117912

#	Time	Username	Problem	Language	Result	Execution time	Memory
117912		Mahdi_Jfri	Gap (APIO16_gap)	C++14	100 / 100	61 ms	2040 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

ll a[maxn];

long long findGap(int T, int n)
{
	if(T == 1)
	{
		ll l = 0 , r = 1e18;
		for(int i = 0; i < (n + 1) / 2; i++)
		{
			ll x , y;
			MinMax(l , r , &x , &y);
			a[i] = x;
			a[n - i - 1] = y;
			l = x + 1 , r = y - 1;
		}

		ll res = 0;
		for(int i = 1; i < n; i++)
			res = max(res , a[i] - a[i - 1]);

		return res;
	}

	ll l ,r;
	MinMax(1LL , 1000000000LL * 1000000000 , &l , &r);
	ll res = (r - l + n - 2) / (n - 1);

	ll a = l;
	l++;
	while(l < r)
	{
		ll s , t;
		MinMax(l , l + res , &s , &t);
		if(s == -1)
		{
			l += res + 1;
			continue;
		}

		res = max(res , s - a);
		a = t;
		l = t + 1;
	}
	return res;
}

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