Submission #501476

#	Time	Username	Problem	Language	Result	Execution time	Memory
501476		Stickfish	Gap (APIO16_gap)	C++17	48.44 / 100	64 ms	3880 KiB

gap

#include "gap.h"
#include <vector>
#include <algorithm>
using ll = long long;
using namespace std;

const ll INF = 1.77013e18;

void find_recur(ll mn, ll mx, ll& maxdif) {
    if (mx - mn <= maxdif)
        return;
    if (mx - mn == 2) {
        ll nmn, nmx;
        MinMax(mn + 1, mx - 1, &nmn, &nmx);
        if (nmn == -1)
            maxdif = max(maxdif, 2ll);
        return;
    } 
    ll md = (mn + mx) / 2;
    ll lmn, lmx;
    MinMax(mn + 1, md, &lmn, &lmx);
    ll rmn, rmx;
    MinMax(md + 1, mx - 1, &rmn, &rmx);

    if (lmn == -1 && rmn == -1) {
        maxdif = max(maxdif, mx - mn);
        return;
    }
    if (lmn == -1) {
        maxdif = max(maxdif, rmn - mn);
        return;
    }
    if (rmn == -1) {
        maxdif = max(maxdif, mx - lmx);
        return;
    }
    maxdif = max({maxdif, lmn - mn, rmn - lmx, mx - rmx});
    if (lmx - lmn < rmx - rmn) {
        find_recur(rmn, rmx, maxdif);
        find_recur(lmn, lmx, maxdif);
    } else {
        find_recur(lmn, lmx, maxdif);
        find_recur(rmn, rmx, maxdif);
    }
}

ll findGap(int T, int N) {
    if (T == 1) {
        vector<ll> mn;
        vector<ll> mx;
        while (mn.size() + mx.size() < N) {
            ll nmn, nmx;
            if (mn.empty()) {
                MinMax(1ll, INF, &nmn, &nmx);
            } else {
                MinMax(mn.back() + 1, mx.back() - 1, &nmn, &nmx);
            }
            mn.push_back(nmn);
            if (nmn != nmx)
                mx.push_back(nmx);
        }
        reverse(mx.begin(), mx.end());
        for (auto x : mx) {
            mn.push_back(x);
        }
        ll ans = 0;
        for (int i = 0; i + 1 < N; ++i) {
             ans = max(ans, mn[i + 1] - mn[i]);
        }
        return ans;
    } else if (N <= 10) {
        ll mn, mx;
        MinMax(1ll, INF, &mn, &mx);
        ll ans = (mx - mn - 1) / (N - 1) + 1;
        find_recur(mn, mx, ans);
        return ans;
    } else {
        ll sgcnt = N * 7 / 4;
        ll sglen = (INF - 2) / N + 1;
        vector<ll> mn(sgcnt);
        vector<ll> mx(sgcnt);
        for (ll i = 0; i < sgcnt; ++i) {
            MinMax(1 + i * sglen, (i + 1) * sglen, &mn[i], &mx[i]);
        }
        ll ans = 0;
        for (int i = 0; i + 1 < sgcnt; ++i) {
            if (mn[i] == -1)
                continue;
            int j = i + 1;
            while (mn[j] == -1 && j < sgcnt)
                ++j;
            if (j != sgcnt) {
                ans = max(ans, mn[j] - mx[i]);
            }
        }
        for (int i = 0; i < sgcnt; ++i) {
            if (mn[i] != -1)
                find_recur(mn[i], mx[i], ans);
        }
        return ans;
    }
    return 0;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:51:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         while (mn.size() + mx.size() < N) {
      |                ~~~~~~~~~~~~~~~~~~~~~~^~~

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