Submission #96256

#	Time	Username	Problem	Language	Result	Execution time	Memory
96256		xplus2g4	Gap (APIO16_gap)	C++11	30 / 100	104 ms	3704 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, ans=1;
    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)/N,x,y;
        a[cnt++]=mn;
        for(s=mn+1, t=s+d; s<mx; s=t+1, t=s+d){
            MinMax(s, min(t, mx-1), &x, &y);
            if (x == -1)
                continue;
            a[cnt++]=x;
            a[cnt++]=y;
        }
        a[cnt++]=mx;
    }
    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