Submission #96253

#	Time	Username	Problem	Language	Result	Execution time	Memory
96253		xplus2g4	Gap (APIO16_gap)	C++11	30 / 100	78 ms	1916 KiB

gap

#include <algorithm>
#include "gap.h"
using namespace std;
typedef long long ll;
ll a[100005];
long long findGap(int T, int N){
    ll mn, mx, s=0, t=1e18;
    int cnt=0;
    if(T==1){
        ll l=0, r=N-1;
        while(l<=r){
            MinMax(s,t,&mn,&mx);
            a[l++]=mn;
            a[r--]=mx;
            s=mn+1;
            t=mx-1;
        }
        cnt=N;
    } else {
        MinMax(s,t,&mn,&mx);
        ll d=(mx-mn)/(N-1), ans = d, last=mn;
        for(ll i=a[0]+1; i<=mx; i+=d+1){
            MinMax(i,i+d,&s,&t);
            if(s!=-1){
                ans = max(ans , s - last) , last = mx;
            }
        }
        return ans;
    }
    ll ans=1;
    for(int i=1; i<cnt; i++){
        ans = max(ans, a[i]-a[i-1]);
    }
    return ans;
}

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