Submission #400625

#TimeUsernameProblemLanguageResultExecution timeMemory
400625FalconGap (APIO16_gap)C++17
100 / 100
69 ms1936 KiB
#include "gap.h" #include <algorithm> #include <iostream> #include <vector> #include <cassert> long long findGap(int T, int N) { if(T == 1) { std::vector<long long> a; a.reserve(N); long long s{0}, e{(long long)1e18}; while(int(a.size()) < N) { MinMax(s, e, &s, &e); assert(s != -1); a.push_back(s); a.push_back(e); ++s, --e; } std::sort(a.begin(), a.end()); long long ans{}; for(int i{}; i < int(a.size()) - 1; ++i) ans = std::max(ans, a[i + 1] - a[i]); return ans; } long long a1{}, aN{}; MinMax(0, (long long)1e18, &a1, &aN); long long d = (aN - a1 + N - 2) / (N - 1), ans = d; for(long long i = a1, p = a1; i <= aN; i += d + 1) { long long s{}, e{}; MinMax(i, std::min(i + d, aN), &s, &e); if(~s) ans = std::max(ans, s - p), p = e; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...