Submission #47679

#	Time	Username	Problem	Language	Result	Execution time	Memory
47679		tieunhi	Gap (APIO16_gap)	C++14	100 / 100	74 ms	1536 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

long long findGap(int T, int N)
{
    long long mn, mx, mmn, mmx;
    MinMax(0, 2e18, &mn, &mx);
    long long res = 0;
    if (T == 1)
    {
        for (int i = 1; i < (N+1)/2; i++)
        {
            MinMax(mn+1, mx-1, &mmn, &mmx);
            if (mmn == -1) break;
            res = max({res, mmn-mn, mx-mmx});
            mn = mmn;
            mx = mmx;
        }
        res = max(res, mx - mn);
    }
    else
    {
        long long sz = (mx - mn + N - 1)/N;
        long long last = mn;
        for (long long b = mn+1, e = mn+sz; ; b += sz, e += sz)
        {
            if (e >= mx) e = mx - 1;
            if (b > e) break;
            MinMax(b, e, &mmn, &mmx);
            if (mmn == -1) continue;
            res = max(res, mmn - last);
            last = mmx;
        }
        res = max(res, mx - last);
    }
    return res;
}

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