제출 #525955

#제출 시각아이디문제언어결과실행 시간메모리
525955vonatlusGap (APIO16_gap)C++17
30 / 100
56 ms1868 KiB
#include "gap.h" #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; pair<ll, ll> ask(ll l, ll r) { ll nl, nr; MinMax(l, r, &nl, &nr); return {nl, nr}; } long long findGap(int T, int n) { ll ans = 0; if (T == 1) { vector<ll> a(n); ll l = 0, r = 1e18; for (int i = 0; i < (n+1)/2; ++i) { ll nl, nr; MinMax(l, r, &nl, &nr); a[i] = nl; a[n-i-1] = nr; l = a[i]+1, r = a[n-i-1]-1; } for (int i = 1; i < n; ++i) { ans = max(ans, a[i]-a[i-1]); } } else { auto [x, y] = ask(0, 1e18); ll B = (y-x)/(n-1), prv = x; for (ll i = x; i <= y; i += B+1) { auto [a, b] = ask(i, i+B); if (a != -1) { ans = max(ans, a-prv); prv = b; } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...