Submission #133247

#	Time	Username	Problem	Language	Result	Execution time	Memory
133247		mlyean00	Gap (APIO16_gap)	C++14	89.12 / 100	73 ms	3064 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll findGap(int T, int N) {
    ll ans = 0;

    ll mn, mx;
    MinMax(0, 1'000'000'000'000'000'000LL, &mn, &mx);

    if (T == 1) {
        for (int i = 1; i < (N + 1) / 2; ++i) {
            ll mn2, mx2;
            MinMax(mn + 1, mx - 1, &mn2, &mx2);
            ans = max({ans, mn2 - mn, mx - mx2});
            mn = mn2;
            mx = mx2;
        }
        ans = max(ans, mx - mn);
    } else if (T == 2) {
        const ll min_gap = 1 + (mx - mn - 1) / (N - 1);
        ll last = mn;

        ll l = mn + 1;
        while (l < mx) {
            ll r = min(mx, l + min_gap);

            ll mn2, mx2;
            MinMax(l, r, &mn2, &mx2);
            if (mn2 != -1) {
                ans = max(ans, mn2 - last);
                last = mx2;
            }

            l += min_gap;
        }

        ans = max(ans, mx - last);
    }

    return ans;
}

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