Submission #1283958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283958		Faisal_Saqib	Gap (APIO16_gap)	C++20	100 / 100	40 ms	3236 KiB

gap

#include "gap.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long findGap(int t, int n)
{
	if(t==1)
	{
		// we can get array
		ll v1,v2;
		ll s=-1,t=1e18+1;
		ll l=0,r=n-1;
		vector<ll> a(n+1);
		while(l<=r)
		{
			MinMax(s,t,&v1,&v2);
			a[l]=v1;
			a[r]=v2;
			l++;
			r--;
			s=v1+1;
			t=v2-1;
		}
		ll mx=0;
		for(int i=1;i<n;i++)
		{
			mx=max(mx,a[i]-a[i-1]);
		}
		return mx;
	}
	else
	{
		ll mi,mx,v1,v2;
		MinMax(0,1e18,&mi,&mx);
		if(n==2)
			return mx-mi;
			// [mi+1,mx-1]
			// mx-mi-1
		ll len=(mx-mi+n-1)/(n-1);
		ll last=mi,ans=0;;
		for(ll cmi=mi+1,cmx=mi+len,i=1;i<n;i++,cmi+=len,cmx+=len)
		{
			if(cmx>=mx)cmx=mx-1;
			if(cmi<=cmx)
			{
				MinMax(cmi,cmx,&v1,&v2);
				if(v1!=-1)
				{
					ans=max(ans,v1-last);
					last=v2;
				}
			}
			else{
				break;
			}
		}
		ans=max(ans,mx-last);
		return ans;
		// mx-mi
	}
	return 0;
}

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