# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
252660 | ChrisT | Gap (APIO16_gap) | C++17 | 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<bits/stdc++.h>
using namespace std;
#include "gap.h"
long long findGap (int t, int n) {
if (t == 1) {
vector<long long> arr(n+1);
long long low = -1, high = 1e18+1;
for (int i = 1; i <= (n+1)/2; i++) {
MinMax(low+1,high-1,low,high);
arr[i] = low; arr[n-i+1] = high;
}
long long mx = 0;
for (int i = 1; i < n; i++) {
mx = max(mx,arr[i+1] - arr[i]);
}
return mx;
} else {
long long mx,mn;
MinMax(0,1e18,mn,mx);
long long go = max(1LL,(mx - mn) / n - 1), ret = 0, lstmx = -1;
for (long long cur = mn; cur <= mx; cur += go) {
long long ed = min(cur + go-1,mx);
long long low,high;
MinMax(cur,ed,low,high);
if (low != -1) {
if (~lstmx) ret = max(ret,low - lstmx);
lstmx = high;
}
}
return ret;
}
}