Submission #381915

#	Time	Username	Problem	Language	Result	Execution time	Memory
381915		ijxjdjd	Gap (APIO16_gap)	C++14	86.31 / 100	84 ms	1900 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using ll = long long;

long long findGap(int T, int N)
{

    if (T == 1) {
        ll low = 0;
        ll high = (ll)(1e18);
        ll arr[N];
        int l = 0;
        int r = N-1;
        while (l <= r) {
            MinMax(low, high, &low, &high);
            arr[l++] = low;
            arr[r--] = high;
            low++;
            high--;
        }
        ll mx = 0;
        for (int i = 1; i < N; i++) {
            mx = std::max(mx, arr[i] - arr[i-1]);
        }
        return mx;
    }
    else {
        ll first = 0;
        ll last = 0;
        MinMax(first, (ll)(1e18), &first, &last);
        ll d = (last-first + N-2)/(N-1);
        ll ans = 0;
        ll next = first+d;
        first++;
        while (first < last) {
            ll mn, mx;
            MinMax(first, next, &mn, &mx);
            if (mn != -1) {
                ans = std::max(mn - (first-1), ans);
                first = mx+1;
                next = mx;
            }
            next += d;
        }
        return ans;
    }
}

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