# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
96004 | oolimry | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "gap.h"
long long findGap(int T, int N)
{
if(T == 1){
long long arr[N];
int x = 0;
long long a, b;
a = 0;
b = 1000000000000000005;
long long mn, mx;
while(true){
MinMax(a,b,&mn,&mx);
arr[x] = mn;
arr[N-x-1] = mx;
a = mn + 1;
b = mx - 1;
x++;
if ((x >= (N+1)/2)) break;
}
long long mm = 0;
for(int i = 0;i < N-1;i++){
mm = std::max(mm,arr[i+1]-arr[i]);
}
return mm;
}
else{
long long a, b;
a = 0;
b = 1000000000000000005;
long long mn, mx;
MinMax(a,b,&mn,&mx);
std::vector<long long> v;
v.push_back(mn);
v.push_back(mx);
long long dist = mx - mn - 2;
long long small = dist / (N-1);
long long big = small+1;
a = mn + 1;
for(int i = 0;i < N-1;i++){
if(i < dist % (N-1)) b = a + big;
else b = a + small;
MinMax(a,b-1,&mn,&mx);
//printf("%lld %lld\n",a,b-1);
if(mn != -1){
v.push_back(mn);
v.push_back(mx);
}
a = b;
}
long long mm = 0;
sort(v.begin(),v.end());
for(int i = 0;i < v.size()-1;i++){
mm = std::max(mm,v[i+1]-v[i]);
}
return mm;
}
}