Submission #113414

#	Time	Username	Problem	Language	Result	Execution time	Memory
113414		imyujin	Gap (APIO16_gap)	C++14	48.54 / 100	69 ms	2808 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 a[MAXN];
    long long b[MAXN];
    long long ans=0;
    long an;
    
    a[0]=-1;
    MinMax(0, INF, a+1, a+2);
    b[0]=a[1];
    for(int i=1; i<N; i++){
        if(i<=(a[2]-a[1])%(N-1)) b[i]=b[i-1]+(a[2]-a[1])/(N-1)+1;
        else b[i]=b[i-1]+(a[2]-a[1])/(N-1);
    }
    
    for(int i=0; i<N-1; i++) MinMax(b[i], b[i+1], a+i*2+3, a+i*2+4);
    sort(a, a+2*N+1);
    an=unique(a, a+2*N+1)-a;
    
    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: 48.5411952864 / 70