# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1160929 | Kalata_56 | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
//#include "gap.h"
long long mas[100011];
long long findGap(int T,int N){
if(T==1){
long long maxa=1e18+1;
long long ans=0;
long long l=0,r=1e18;
long long L=0,R=N-1;
while(L<=R){
//long long k1,k2;
MinMax(l,r,&mas[L],&mas[R]);
L++;
R--;
l=mas[L-1]+1;
r=mas[R+1]-1;
}
for(int i=0;i<N-1;i++){
if(mas[i+1]-mas[i]>ans){
ans=mas[i+1]-mas[i];
}
}
return ans;
}
long long k1,k2;
long long l=0,r=1e18;
MinMax(l,r,&k1,&k2);
if(N==2){
return k2-k1;
}
l=k1+1;
r=k2-1;
long long dul=(r-l+1)/(N-1);
long long L=l,R=L+dul-1;
long long pre=l-1;
long long otg=0;
for(int i=0;i<N-1;i++){
MinMax(L,R,&k1,&k2);
otg=max(otg,(k1-pre));
pre=k2;
L+=dul;
R=L+dul-1;
}
return max(otg,(r+1)-pre);
}