Submission #96248

#	Time	Username	Problem	Language	Result	Execution time	Memory
96248		xplus2g4	Gap (APIO16_gap)	C++11	100 / 100	86 ms	2680 KiB

gap

#include "gap.h"
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
typedef long long ll;
ll a[MAX_N*2];
long long findGap(int T, int N)
{
    ll ans = 1, s = 0, t = 1e18, mn, mx;
    int n = 0;
    if (T == 1) {
        ll head = 0, tail = N-1;
        while (head <= tail) {
            MinMax(s, t, &mn, &mx);
            a[head++] = mn;
            a[tail--] = mx;
            s = mn+1;
            t = mx-1;
        }
        n = N;
    } else {
        MinMax(s, t, &mn, &mx);
        ll d = (mx-mn+N-1)/N, x, y;
        a[n++] = mn;
        for (s = mn+1, t = s+d; s < mx; s = t+1, t = s+d) {
            MinMax(s, min(t, mx-1), &x, &y);
            if (x == -1)
                continue;
            a[n++] = x;
            a[n++] = y;
        }
        a[n++] = mx;
    }
    for (int i = 1; i < n; ++i)
        ans = max(ans, a[i] - a[i-1]);

    return ans;
}

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