Submission #96249

#	Time	Username	Problem	Language	Result	Execution time	Memory
96249		xplus2g4	Gap (APIO16_gap)	C++11	30 / 100	59 ms	3576 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);
        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: 30 / 30
• Subtask 2: 0 / 70