Submission #26407

#	Time	Username	Problem	Language	Result	Execution time	Memory
26407		zscoder	Gap (APIO16_gap)	C++14	100 / 100	79 ms	5924 KiB

gap

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

ll a[100001];

long long findGap(int T, int N)
{
	if(T == 1)
	{
		int l = 0; int r = N - 1;
		ll al, ar;
		al = 0; ar = ll(1e18);
		ll m, n;
		for(int i = 0; i < (N+1)/2; i++)
		{
			MinMax(al, ar, &m, &n);
			a[l] = m;
			a[r] = n;
			l++; r--;
			al = m + 1; ar = n - 1;
		}
		ll ans = 0;
		for(int i = 1; i < N; i++)
		{
			ans = max(ans, a[i] - a[i - 1]);
		}
		return ans;
	}
	else
	{
		ll amin; ll amax;
		ll m, n;
		ll maxd = 0;
		MinMax(0, ll(1e18), &amin, &amax);
		a[0] = amin;
		a[N - 1] = amax;
		if(N == 2) return (amax - amin);
		if(amax - amin == N - 1)
		{
			return 1;
		}
		ll curL = amin;
		ll l = amin + 1; ll r;
		ll d = amax - amin - 1;
		ll q = d/(N - 1);
		ll rem = d%(N - 1);
		for(int i = 0; i < N - 1; i++)
		{
			if(i < rem)
			{
				r = l + q;
			}
			else
			{
				r = l + q - 1;
			}
			MinMax(l, r, &m, &n);
			if(!(m == -1 && n == -1))
			{
				maxd = max(maxd, m - curL);
				curL = n;
			}
			l = r + 1;
		}
		maxd = max(maxd, amax - curL);
		//Remember to d the last element
		return maxd;
	}
}

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