Submission #554420

#	Time	Username	Problem	Language	Result	Execution time	Memory
554420		gimabd30	Gap (APIO16_gap)	C++17	100 / 100	62 ms	1872 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll findGap(int T, int N) {
    const ll inf = 1'000'000'000'000'000'000LL;
    ll mn = -1, mx  = inf + 1;
    if (T == 1) {
        vector<ll> a(N);
        ll ans = -inf;
        for (int l = 0, r = N - 1; l <= r; ++l, --r) {
            MinMax(mn + 1, mx - 1, &mn, &mx);
            assert(mn != -1);
            a[l] = mn, a[r] = mx;
        }
        for (int i = 0; i < N - 1; ++i) {
            ans = max(ans, a[i + 1] - a[i]);
        }
        return ans;
    } else {
        MinMax(0, inf, &mn, &mx);
        ll sum = mx - mn;
        ll ans = -inf;
        ll len = (sum + (N - 1) - 1) / (N - 1);
        ll R = mx;
        for (int i = N - 1; i > 0; --i) {
            ll nw = mx;
            MinMax(mx - len, mx - 1, &mn, &mx);
            if (mx != -1) {
                ans = max(ans, R - mx);
                R = mn;
            }
            mx = nw - len;
        }
        return ans;
    }
}

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