Submission #113411

#	Time	Username	Problem	Language	Result	Execution time	Memory
113411		imyujin	Gap (APIO16_gap)	C++14	0 / 100	76 ms	10128 KiB

gap

#include "gap.h"
#include<algorithm>

using namespace std;

#define MAXN 100005

const long long INF=1e18;

long long findGap(int T, int N)
{
    long long s, e;
    long long b[MAXN];
    long long mn[MAXN], mx[MAXN];
    long long a[MAXN], an;
    long long ans=0;
    
    MinMax(0, INF, &s, &e);
    b[0]=s;
    for(int i=1; i<N; i++){
        if(i<=(e-s)%(N-1)) b[i]=b[i-1]+(e-s)/(N-1)+1;
        else b[i]=b[i-1]+(e-s)/(N-1);
    }
    
    for(int i=0; i<N-1; i++) MinMax(b[i], b[i+1], mn+i, mx+i);
    a[0]=-1;
    a[1]=s;
    a[2]=e;
    an=3;
    for(int i=0; i<N-1; i++) if(mn[i]!=-1){
        a[an++]=mn[i];
        a[an++]=mx[i];
    }
    sort(a, a+an);
    unique(a, a+an);
    
    for(int i=1; i<an-1; i++) if(a[i+1]-a[i]>ans) ans=a[i+1]-a[i];
    return ans;
}

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