제출 #560785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
560785		abcvuitunggio	Gap (APIO16_gap)	C++17	43.80 / 100	111 ms	1984 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long f(long long l, long long r){
    if (l>=r)
        return -1;
    long long mn,mx,mn2,mx2,mid=(l+r)>>1;
    MinMax(l,mid,&mn,&mx);
    if (mn==-1)
        return f(mid+1,r);
    MinMax(mid+1,r,&mn2,&mx2);
    if (mn2==-1)
        return f(mn,mx);
    return max(max(mn2-mx,f(mn,mx)),f(mn2,mx2));
}
long long findGap(int T, int N)
{
    long long a[N],lo=0,hi=1000000000000000000,res=0;
    if (T==1){
        for (int i=0;i<N&&i<=N-i-1;i++){
            MinMax(lo,hi,&a[i],&a[N-i-1]);
            lo=a[i]+1;
            hi=a[N-i-1]-1;
        }
        for (long long i=0;i<N-1;i++)
            res=max(res,a[i+1]-a[i]);
        return res;
    }
    return f(lo,hi);
}

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