Submission #546393

#	Time	Username	Problem	Language	Result	Execution time	Memory
546393		marsxiang5902	Gap (APIO16_gap)	C++14	Compilation error	0 ms	0 KiB

gap

#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

Compilation message (stderr)

gap.cpp: In function 'll solve1()':
gap.cpp:38:9: error: 'MinMax' was not declared in this scope
   38 |         MinMax(pvMn + 1, pvMx - 1, pvMn, pvMx);
      |         ^~~~~~
gap.cpp: In function 'll solve2()':
gap.cpp:45:5: error: 'MinMax' was not declared in this scope
   45 |     MinMax(0, MX, mn, mx);
      |     ^~~~~~