제출 #456445

#제출 시각아이디문제언어결과실행 시간메모리
456445nonsensenonsense1Gap (APIO16_gap)C++17
0 / 100
64 ms1108 KiB
#include "gap.h" #include <cassert> #include <algorithm> const long long N = 1000000000000000000; long long task1(int n) { long long l = 0, r = N, ans = 0; for (int i = 0; i * 2 < n; ++i) { long long ll, rr; MinMax(l, r, &ll, &rr); if (l) ans = std::max(ans, ll - l + 1); if (r != N) ans = std::max(ans, r - rr + 1); if (i * 2 == n - 2) ans = std::max(ans, rr - ll); l = ll + 1; r = rr - 1; } return ans; } inline long long d(int n, int k, long long l, long long r) { return l + (__int128)(r - l) * k / n; } long long task2(int n) { long long l, r; MinMax(0, N, &l, &r); if (n == 2) return r - l; ++l; long long pr = l, ans = 0, len = d(n - 2, 1, l, r) - d(n - 2, 0, l, r); for (int i = 0; i < n - 2; ++i) { long long ll, rr; assert(abs(len - d(n - 2, i + 1, l, r) + d(n - 2, i, l, r)) <= 1); MinMax(d(n - 2, i, l, r), d(n - 2, i + 1, l, r) - 1, &ll, &rr); if (ll != -1) { ans = std::max(ans, ll - pr); pr = rr; } } return std::max(ans, r - pr); } long long findGap(int t, int n) { assert(n > 2); if (t == 1) return task1(n); return task2(n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...