Submission #400075

#	Time	Username	Problem	Language	Result	Execution time	Memory
400075		dxz05	Gap (APIO16_gap)	C++14	55.47 / 100	79 ms	1232 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 555555;
const long long INF = 1e18 + 2e2;

typedef long long ll;

ll a[MAXN];

long long findGap(int SUBTASK, int n){
    ll mn, mx;
    MinMax(0, INF, &mn, &mx);

    a[1] = mn;
    a[n] = mx;

    ll x = (mx - mn + n - 2) / (n - 1);
    ll ans = x;

    ll l = mn, last = mn;
    while (l <= a[n]){
        MinMax(l + 1, l + x, &mn, &mx);
        if (mn == -1){
            l += x;
        } else {
            ans = max(ans, mn - last);
            l = last = mx;
        }
    }

    return ans;
}

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