Submission #501485

#TimeUsernameProblemLanguageResultExecution timeMemory
501485StickfishGap (APIO16_gap)C++17
100 / 100
46 ms3220 KiB
#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) {
      |                ~~~~~~~~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...