Submission #546395

#	Time	Username	Problem	Language	Result	Execution time	Memory
546395		marsxiang5902	Gap (APIO16_gap)	C++14	100 / 100	104 ms	5860 KiB

gap

#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

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70