Submission #96246

#	Time	Username	Problem	Language	Result	Execution time	Memory
96246		xplus2g4	Gap (APIO16_gap)	C++11	0 / 100	80 ms	3728 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;
    int cnt=0;
    if(T==1){
        MinMax(0,1e18,&a[0],&a[N-1]);
        ll l=1, r=N-2;
        while(l<=r){
            MinMax(a[l]+1,a[r]-1,&mn,&mx);
            a[l++]=mn;
            a[r--]=mx;
        }
        cnt=N;
    } else {
        MinMax(0,1e18,&mn,&mx);
        ll d=(mx-mn)/(N-1);
        a[cnt++]=mn;
        for(ll i=a[0]+1; i<mx; i+=d+1){
            ll x,y;
            MinMax(i,i+d,&x,&y);
            if(x!=-1){
                a[cnt++]=x;
                a[cnt++]=y;
            }
        }
        a[cnt++]=mx;
    }
    ll ans=1;
    for(int i=1; i<cnt; i++){
        ans = max(ans, a[i]-a[i-1]);
    }
    return ans;
}

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