| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1343809 | Newtonabc | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#include "gap.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long findGap(int T, int N)
{
if(T==2){
vector<pair<ll,ll>> v;
long long n=N;
ll mn,mx;
ll tmp=1e18;
MinMax(1LL,tmp,&mn,&mx);
ll l=mn,r=mx;
long long rng=r-l;
long long sz=(rng+n-2LL)/(n-1LL);
for(ll i=l+sz;i<=r+sz-1;i+=sz+1LL){
ll lb=i-sz;
ll sec=i/sz;
//cout<<lb <<" " <<i <<"\n";
MinMax(lb,i,&mn,&mx);
if(mn!=-1) v.push_back({mn,mx});
}
ll ans=sz;
for(int i=0;i<(int)(v.size())-1;i++){
ans=max(ans,v[i+1].first-v[i].second);
}
return ans;
}
else{
long long s=-1;
long long t=(long long)1e18+1;
long long x=-1;
long long y=-1;
ll n=N;
long long maxi=LLONG_MIN;
for(int i=1;i<=n/2;i++){
MinMax(s+1,t-1,&s,&t);
v.push_back(t);
v.push_back(s);
}
if(n%2==1){
MinMax(s+1,t-1,&s,&t);
v.push_back(s);
}
int i=1;
long long xx;
sort(v.begin(),v.end());
for(auto a:v){
if(i!=1){
maxi=max(maxi,a-xx);
}
i++;
xx=a;
}
return maxi;
}
return 0;
}
