Submission #1283909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283909		Faisal_Saqib	Gap (APIO16_gap)	C++20	43.98 / 100	216 ms	5112 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 v1,v2;
		ll s=-1;
		ll l=0,r=n-1;
		set<ll> vals={1000000000000000000};
		vector<ll> a(n+1);
		while(l<=r)
		{
			// cout<<"CUr "<<l<<' '<<r<<' '<<s<<endl;
			ll ts=s,te=*(vals.upper_bound(s));
			v1=te;
			// cout<<"Range for r "<<ts<<' '<<te<<endl; 
			while(ts+1<te)
			{
				ll mid=(ts+te)/2;
				// cout<<ts<<' '<<te<<' '<<mid<<endl;
				MinMax(s+1,mid,&v1,&v2);
				if(v1==v2 and v1==-1)
				{
					// this means that there are no value in the range [s,mid]
					// a[l] is in range [s+1,1e18]
					s=mid;
					ts=mid;
					v1=te;
				}
				else
				{
					vals.insert(v2);
					break;
					// a[l] = v1
					// val less than 
				}
			}
			a[l]=v1;
			// cout<<"ind: "<<l<<' '<<v1<<endl;
			l++;
			s=v1;
		}
		ll mx=0;
		for(int i=1;i<n;i++)
		{
			mx=max(mx,a[i]-a[i-1]);
		}
		return mx;		
	}
	return 0;
}

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