| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 152571 | Ruxandra985 | 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 <cstdio>
#include "gap.h"
long long findGap (int t , int n){
long long l,r,i;
long long st,dr,a,b,sol,x,y,mid,last;
if (t == 1){
long long w[100010];
st = 1;
dr = 1000000000000000000;
l = 1;
r = n;
while (l<=r){
a=b=0;
MinMax (st,dr,&a,&b);
if (l < r){
w[l] = a;
w[r] = b;
}
else {
w[l] = a;
}
st = a + 1;
dr = b - 1;
l++;
r--;
}
sol = 0;
for (i=2;i<=n;i++){
if (sol < w[i] - w[i-1])
sol = w[i] - w[i-1];
}
return sol;
}
else {
MinMax (0,1000000000000000000,a,b);
l = a;
r = b;
sol = 0;
while (l <= b && b - l > sol){ /// daca dif e mai mica , irelevant
/// as vrea sa trec in urmatorul la o distanta > sol
MinMax (l , l + sol , &x , &y);
if (x < y){ /// exista ceva , skip
l = y;
}
else { /// e doar l
st = sol + 1;
dr = b - l;
while (st<=dr){
mid = (st + dr)/2;
MinMax (l , l + mid , &x , &y);
if (y == l){ /// vreau mai mare
st = mid + 1;
}
else {
last = y;
dr = y - l - 1;
}
}
sol = last - l;
l = last;
}
}
return sol;
}
}