Submission #1297308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297308		denislav	Gap (APIO16_gap)	C++20	41.97 / 100	342 ms	3236 KiB

gap

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
# include "gap.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=2e5+11;

int n;
long long a[MAX];

long long findGap(int T, int _N)
{

    n=_N;

    if(T==1 or n<=30)
    {
        long long l=1,r=n;
        a[0]=-1;
        a[n+1]=INF+1;
        while(l<=r)
        {
            long long mn,mx;
            MinMax(a[l-1]+1,a[r+1]-1,&mn,&mx);
            a[l]=mn;
            a[r]=mx;
            l++;
            r--;
        }

        long long ans=0;
        for(int i=1;i<n;i++) ans=max(ans,a[i+1]-a[i]);
        return ans;
    }

    long long MN,MX;
    MinMax(1LL,(long long)1e18,&MN,&MX);
    long long last=0,ans=0;
    /*
    for(int bit=1;bit<60;bit++)
    {
        long long mn,mx;
        MinMax(last+1,last+(1LL<<bit),&mn,&mx);
        if(mn!=-1)
        {
            last=mn;
            break;
        }
    }
    */

    last=MN;
    while(true)
    {
        //cout<<"->"<<last<<"\n";
        if(last==MX) break;
        for(int bit=1;bit<=60;bit++)
        {
            long long mn,mx;
            long long s=last+1,t=last+(1LL<<bit);
            MinMax(s,t,&mn,&mx);

            if(mn==-1) continue;
            else
            {
                ans=max(ans,mn-last);
                last=mx;
                break;
            }
        }
    }

	return ans;
}

/*
2 4
2 3 6 8
*/

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