Submission #1214926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214926		omsincoconut	Gap (APIO16_gap)	C++17	59.02 / 100	46 ms	3256 KiB

gap

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

using namespace std;
typedef long long ll;

const ll MAXVAL = 1e18;

pair<ll, ll> query(ll l, ll r) {
    ll a, b;
    MinMax(l, r, &a, &b);
    return make_pair(a, b);
}

ll findGap(int T, int N) {
    auto [mi, mx] = query(0, MAXVAL);

    if (N == 2) {
        return mx-mi;
    } else if (N <= 4) {
        auto [a, b] = query(mi+1, mx-1);
        return max({a-mi, b-a, mx-b});
    }

    ll query_range = (mx-mi+N)/N;
    vector<pair<ll, ll>> ranges;
    for (ll lb = mi; lb < mx; lb += query_range) {
        auto [a, b] = query(lb, lb+query_range-1);
        if (a != -1) ranges.emplace_back(a, b);
    }

    ll ans = 0;
    for (int i = 0; i < ranges.size(); i++) {
        ans = max(ans, ranges[i].second - ranges[i].first);
        if (i > 0) ans = max(ans, ranges[i].first - ranges[i-1].second);
    }

    return ans;
}

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