Submission #560830

#	Time	Username	Problem	Language	Result	Execution time	Memory
560830		abcvuitunggio	Gap (APIO16_gap)	C++17	30 / 100	3096 ms	1864 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int T, int N)
{
    long long a[N],mn,mx,mn2,mx2,lo=0,hi=1e18,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;
    }
    MinMax(lo,hi,&mn,&mx);
    long long cur=-1,h=(mx-mn+N-2)/(N-1);
    for (int i=mn;i+h<=mx;i+=h+1){
        MinMax(i,i+h,&mn2,&mx2);
        if (mn2==-1)
            continue;
        if (cur!=-1)
            res=max(res,mn2-cur);
        cur=mx2;
    }
    return res;
}

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