Submission #1012155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012155		codefox	Gap (APIO16_gap)	C++14	64.63 / 100	40 ms	1212 KiB

gap

#include "gap.h"

#define ll long long

long long findGap(int T, int N)
{
    if (T==1)
    {
        ll l = 0;
        ll r = 1e18;
        ll mxdist = 0;
        ll nl = 0;
        ll nr = 0;
        ll fl = -1;
        ll fr = -1;
        for (int j = 0; j < N && l<=r; j+=2)
        {
            MinMax(l, r, &nl, &nr);
            if (nr==-1) break;
            if (fl != -1 && nl-fl>mxdist) mxdist = nl-fl;
            if (fr != -1 && fr-nr>mxdist) mxdist = fr-nr;
            fl = nl;
            fr = nr;
            l = nl+1;
            r = nr-1;
        }
        if (fr-fl>mxdist) mxdist = fr-fl;
        return mxdist;
    }
    else
    {
        ll l = 0;
        ll rr = 0;
        MinMax(0, 1e18, &l, &rr);
        if (N==2) return rr-l;
        ll dd = 1;
        while (l != rr)
        {
            ll sl = -1;
            ll sr = -1;
            MinMax(l+1, l+dd, &sl, &sr);
            while (sr==-1)
            {
                MinMax(l+dd, l+2*dd, &sl, &sr);
                if (sr==-1) dd*=2;
            }
            if (sl-l>dd) dd = sl-l;
            l = sr;
        }
        return dd;
    }
}

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