Submission #501485

#	Time	Username	Problem	Language	Result	Execution time	Memory
501485		Stickfish	Gap (APIO16_gap)	C++17	100 / 100	46 ms	3220 KiB

gap

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

mt19937 rng(time(0));
const ll INF = 1.77013e18;

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 {
        ll mn, mx;
        MinMax(1, INF, &mn, &mx);
        ll ans = (mx - mn - 1) / (N - 1) + 1;
        ll mxans = mx - mn;
        ll curvl = mn;
        vector<pair<ll, ll>> gaps;
        while (ans < mxans && curvl < mx) {
            ll nmn, nmx;
            MinMax(curvl + 1, curvl + ans * 2 - 1, &nmn, &nmx);
            if (nmn != -1) {
                ans = max(ans, nmn - curvl);
                gaps.push_back({nmn, nmx});
                curvl = nmx;
            } else {
                ans *= 2;
            }
        }
        shuffle(gaps.begin(), gaps.end(), rng);
        for (auto [l, r] : gaps) {
            if (r - l > ans) {
                ll md = (l + r) / 2;
                ll lmn, lmx;
                MinMax(l + 1, md, &lmn, &lmx);
                if (lmx != -1 && r - lmx <= ans)
                    continue;
                ll rmn, rmx;
                MinMax(md + 1, r - 1, &rmn, &rmx);
                if (lmn == -1 && rmn == -1) {
                    ans = r - l;
                } else if (lmn == -1) {
                    ans = max(ans, rmn - l);
                } else if (rmn == -1) {
                    ans = max(ans, r - lmx);
                } else {
                    ans = max(ans, rmn - lmx);
                }
            }
        }
        return ans;
    }
    return 0;
}

Compilation message (stderr)

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

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