Submission #529805

#	Time	Username	Problem	Language	Result	Execution time	Memory
529805		happypotato	Gap (APIO16_gap)	C++17	30 / 100	50 ms	1088 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mn, mx;
ll st1(int n) {
    ll s = 0, t = 1e18;
    MinMax(s, t, &mn, &mx);
    ll ans = 0;
    for (ll i = 2; i <= n / 2; i++) {
        ll pmn = mn, pmx = mx;
        MinMax(mn + 1, mx - 1, &mn, &mx);
        ans = max(ans, mn - pmn);
        ans = max(ans, pmx - mx);
    }
    if (n % 2 == 1) {
        ll fin, fin2;
        MinMax(mn + 1, mx - 1, &fin, &fin2);
        ans = max(ans, fin - mn);
        ans = max(ans, mx - fin);
    } else {
        ans = max(ans, mx - mn);
    }
    return ans;
}
ll st2(int n) {
    if (n <= 5) return st1(n);
    /*
    Solution outline:
    Query(0, 1e18) -> n + 1 queries
    n - 2 items left, given a[1] and a[n]
    Idea:
    spilt the range into n - 1
    by pigeonhole principle, at least 1 range has no items
    (and there definitely exists a range which is >= that range)
    Take max(min of right range - max of left range)
    */
    ll s = 0, t = 1e18;
    MinMax(s, t, &mn, &mx);
    s = mn + 1; t = mx - 1;
    ll range = (t - s) + 1;
    range /= (n - 1);
    // fprintf(stderr, "Range: %lld\n", range);
    ll int rs = s, rt = s + range - 1;
    ll int prev = mn;
    ll int ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        MinMax(rs, rt, &mn, &mx);
        // fprintf(stderr, "Query: %lld %lld, return: %lld %lld\n", rs, rt, mn, mx);
        rs += range; rt += range;
        if (mn == -1) continue;
        ans = max(ans, mn - prev);
        prev = mx;
    }
    MinMax(rs, t, &mn, &mx);
    // fprintf(stderr, "[FINAL] Query: %lld %lld, return: %lld %lld\n", rs, t, mn, mx);
    if (mn != -1) {
        ans = max(ans, mn - prev);
        ans = max(ans, (t + 1) - mx);
    } else {
        ans = max(ans, (t + 1) - prev);
    }
    return ans;
}
long long findGap(int T, int N) {
    if (T == 1) return st1(N);
    else return st2(N);
}

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