Submission #842309

#	Time	Username	Problem	Language	Result	Execution time	Memory
842309		popovicirobert	Gap (APIO16_gap)	C++14	100 / 100	37 ms	3876 KiB

gap

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr ll INF =  1e18;

vector<ll> arr;

#ifdef HOME

void MinMax(ll a, ll b, ll* mn, ll* mx) {
    *mn = INF;
    *mx = -INF;
    for (auto itr : arr) {
        if (itr >= a && itr <= b) {
            *mn = min(*mn, itr);
            *mx = max(*mx, itr);
        }
    }
    if (*mn == INF) {
        *mn = -1;
    }
    if (*mx == -INF) {
        *mx = -1;
    }
}

#else
#include "gap.h"
#endif

pair<ll, ll> Query(ll a, ll b) {
    ll mn, mx;
    MinMax(a, b, &mn, &mx);
    return {mn, mx};
}

ll findGap1(int N) {

    vector<ll> a(N + 2);
    a[0] = -1, a[N + 1] = INF + 1;

    int left = 1, right = N;
    while (left <= right) {
        pair<ll, ll> res = Query(a[left - 1] + 1, a[right + 1] - 1);
        a[left] = res.first;
        a[right] = res.second;
        left++, right--;
    }

    ll answer = 0;
    for (int i = 1; i < N; i++) {
        answer = max(answer, a[i + 1] - a[i]);
    }

    return answer;
}

ll findGap2(int N) {
    pair<ll, ll> res = Query(0, INF);
    
    ll a1 = res.first;
    ll an = res.second;
    ll step = (an - a1 + N - 2) / (N - 1);

    ll answer = 0;

    ll curr = a1;
    while (curr < an) {
        
        int x = 0;
        do {
            x++;
            res = Query(curr + 1, curr + step * x);
            if (res.second != -1) {
                break;
            }
        } while (true);

        answer = max(answer, res.first - curr);
        step = max(step, answer);
        curr = res.second;
    }

    return answer;
}

ll findGap(int T, int N) {
    return T == 1 ? findGap1(N) : findGap2(N);
}

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