Submission #35250

#	Time	Username	Problem	Language	Result	Execution time	Memory
35250		nickyrio	Gap (APIO16_gap)	C++14	100 / 100	79 ms	5920 KiB

gap

#include <iostream>
#include "gap.h"
#define n 100010
long long a[n];

long long max(long long a, long long b) {
    return a > b ? a : b;
}

long long findGap(int T, int N)
{
    if (T == 1) {
        MinMax(0, 1e18, &a[1], &a[N]);
        for(int i = 2; i <= (N + 1) / 2; i++) {
            MinMax(a[i - 1] + 1, a[N - i + 2] - 1, &a[i], &a[N - i + 1]);
        }
        long long ans = a[2] - a[1];
        for (int i = 2; i<N; i++) ans = max(ans, a[i + 1] - a[i]);
        return ans;

    }
	long long mn, mx, last, ans = -1;
    MinMax(0, 1e18, &mn, &mx);
    last = mn;
    long long BLOCKSIZE = (mx - mn) / (N - 1);
    if ((mx - mn) % (N - 1)) BLOCKSIZE++;
    bool ok = false;
    for (long long sBLOCK = mn + 1; sBLOCK <= mx;) {
        long long fBLOCK = sBLOCK + BLOCKSIZE - 1;
        if (fBLOCK >= mx) {
            fBLOCK = mx - 1;
            ok = true;
        }
        long long minNow, maxNow;
        if (fBLOCK < sBLOCK) break;
        MinMax(sBLOCK, fBLOCK, &minNow, &maxNow);
        if (minNow == -1) {
            sBLOCK = fBLOCK + 1;
            if (ok) break;
            continue;
        }
        if (minNow == maxNow) ans = max(ans, maxNow - last);
        else ans = max(ans, max(maxNow - minNow, minNow - last));
        last = maxNow;
        sBLOCK = fBLOCK + 1;
        if (ok) break;
    }
    ans = max(ans, mx - last);
    return ans;
}

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