Submission #955625

#	Time	Username	Problem	Language	Result	Execution time	Memory
955625		sleepntsheep	Gap (APIO16_gap)	C11	100 / 100	48 ms	1436 KiB

gap

#include "gap.h"

long long findGap(int t, int n)
{
    if(t==2)
    {
        long long mn,mx;
        MinMax(-1e18,1e18,&mn,&mx);
        long long k=mx-mn;
        long long x = (k+n-1)/n;

        long long z=x,l=mn,ll=l;

        while(l<mx)
        {
            long long p,q;
            MinMax(l+1,l+x,&p,&q);
            if(~p)
            {
                if(p-ll>z)z=p-ll;
                ll=q;
                l+=x;
            }
            else
            {
                l+=x;
            }
        }
        return z;
    }
    else
    {
        long long mn,mx;
        MinMax(-1e18,1e18,&mn,&mx);
        int found;
        if(mn==mx)found=1; else found=2;
        long long z=0;
        if(found==n)z=mx-mn;
        while(found<n&&mx-mn>1)
        {
            long long p,q;
            MinMax(mn+1,mx-1,&p,&q);
            if(p==q)++found;
            else found+=2;
            if(found==n)
                if(q-p>z)z=q-p;
            if(~p)
            {
                if(p-mn>z)z=p-mn;
                if(mx-q>z)z=mx-q;
                mn=p,mx=q;
            }
            else 
            {
                if(mx-mn>z)z=mx-mn;
                break;
            }
        }

        return z;
    }
}

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