Submission #23281

#	Time	Username	Problem	Language	Result	Execution time	Memory
23281		repeating	Gap (APIO16_gap)	C++11	100 / 100	69 ms	4900 KiB

gap

const long long MAXN = 1e18;
long long findGap(int, int);
void MinMax(long long , long long , long long *, long long *);
long long findGap(int T, int N)
{
    if(T == 2)
    {
        long long mmin, mmax;
        MinMax(0LL,MAXN,&mmin,&mmax);
        long long gap = (mmax-mmin-1)/(N-1), res = -1;
        long long L = mmin+1, prevMax = mmin;
        while(L<=mmax)
        {
            long long curMin, curMax;
            MinMax(L,L+gap,&curMin,&curMax);
            if(curMin != -1 && curMax != -1)
            {
                long long curDiff = curMin - prevMax;
                res = (curDiff > res ? curDiff : res);
                prevMax = curMax;
            }
            L += gap+1;
        }
        return res;
    }
    long long aray[N], i = 0, j = N-1, lo = 0, hi = MAXN;
    while(j-i >= 0)
    {
        long long x, y;
        MinMax(lo,hi,&x,&y);
        aray[i] = x, aray[j] = y;
        i++, j--;
        lo = x+1;
        hi = y-1;
    }
 
    long long res = -1;
    for(int i = 0; i+1 < N; i++)
        res = (res < aray[i+1]-aray[i] ? aray[i+1]-aray[i] : res);
    return res;
}

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