Submission #47780

#	Time	Username	Problem	Language	Result	Execution time	Memory
47780		ikura355	Gap (APIO16_gap)	C++14	100 / 100	71 ms	2156 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 5;
const ll inf = 2e18;

ll a[maxn];

ll findGap(int T, int N) {
    if(T==1) {
        ll L = -inf, R = inf;
        for(int i=1,j=N;i<=j;i++,j--) {
            MinMax(L+1,R-1,&L,&R);
            a[i] = L; a[j] = R;
        }
        ll ans = 0;
        for(int i=1;i<N;i++) ans = max(ans, a[i+1]-a[i]);
        return ans;
    }
    else {
        ll L, R;
        MinMax(-inf,inf,&L,&R);
        ll sz = (ll)ceil((double)(R-L-1)/(N-1));
        ll ans = 0, last = L;
        for(ll x=L+1;x<=R-1;x+=sz) {
            ll t1, t2;
            MinMax(x,min(R-1,x+sz-1),&t1,&t2);
            if(t1==-1) continue;
            ans = max(ans, t1-last);
            last = t2;
        }
        ans = max(ans, R-last);
        return ans;
    }
}

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