| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1283905 | Faisal_Saqib | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#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;
}