제출 #113416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113416		imyujin	Gap (APIO16_gap)	C++14	100 / 100	70 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)
{
    if(T==1){
        long long c[MAXN];
        long long ans=0;
        
        MinMax(0ll, INF, c, c+N-1);
        for(int i=1; i<(N+1)/2; i++) MinMax(c[i-1]+1, c[N-i]-1, c+i, c+N-i-1);
        for(int i=0; i<N-1; i++) if(c[i+1]-c[i]>ans) ans=c[i+1]-c[i];
        return ans;
    }
    else{
        long long a[MAXN];
        long long b[MAXN];
        long long ans=0;
        long an;
        
        a[0]=-1;
        MinMax(0ll, INF, a+1, a+2);
        b[0]=a[1]-1;
        for(int i=1; i<N; i++){
            if(i<=(a[2]-a[1]+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]+1)/(N-1);
        }
        
        for(int i=0; i<N-1; i++) MinMax(b[i]+1, 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: 30 / 30
• Subtask 2: 70 / 70