| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 546394 | marsxiang5902 | 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.
#ifndef LOCAL_PROJECT
#include "gap.h"
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MN = 2e5+5;
const ll MX = ll(1e9) * ll(1e9);
#ifdef LOCAL_PROJECT
int __T, __N; ll ar[MN], M = 0;
void MinMax(ll s, ll t, ll &mn, ll &mx){
++M;
int a = lower_bound(ar, ar+__N, s) - ar, b = upper_bound(ar, ar+__N, t) - ar - 1;
if(a > b){
mn = mx = -1;
return;
}
if(__T == 2)
M += b-a+1;
mn = ar[a]; mx = ar[b];
}
#endif
int N;
set<ll> ans;
void add(ll x){ ans.insert(x); }
void add(vector<ll> x){ ans.insert(x.begin(), x.end()); }
ll getAns(){
ans.erase(-1);
ll ret = 0;
for(auto it = ans.begin(), it2 = next(it); it2 != ans.end(); it++, it2++)
ret = max(ret, *it2 - *it);
return ret;
}
ll solve1(){
ll pvMn = -1, pvMx = MX+1;
for(int l = 0, r = N-1; l <= r; l++, r--){
MinMax(pvMn + 1, pvMx - 1, pvMn, pvMx);
add({pvMn, pvMx});
} return getAns();
}
ll solve2(){
ll mn, mx;
MinMax(0, MX, mn, mx);
ll mnAns = (mx-mn) / (N-1) + 1;
add({mn, mx});
for(ll i = mn+1, a, b; i < mx; i += mnAns){
MinMax(i, min(i + mnAns, mx) - 1, a, b);
add({a, b});
}
return getAns();
}
ll findGap(int T, int _N){
N = _N;
return T == 1 || N <= 7 ? solve1() : solve2();
}
#ifdef LOCAL_PROJECT
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> __T >> __N;
for(int i = 0; i < __N; i++)
cin >> ar[i];
sort(ar, ar+__N);
ll res = findGap(__T, __N);
printf("%lld %lld\n", res, M);
ll realAns = 0;
for(int i = 0; i < __N-1; i++)
realAns = max(realAns, ar[i+1] - ar[i]);
assert(res == realAns && (__T == 1 ? M <= (__N+1) / 2 : M <= 3*__N));
return 0;
}
#endif