제출 #199990

#제출 시각아이디문제언어결과실행 시간메모리
199990Osama_AlkhodairyGap (APIO16_gap)C++17
32.81 / 100
85 ms1284 KiB
#include <bits/stdc++.h> #include "gap.h" //~ #include "grader.cpp" using namespace std; #define ll long long ll ans; ll mn, mx; void solve(ll l, ll r){ if(ans > r - l + 2) return; if(l == r) return; ll d = r - l; vector <ll> s; for(int i = 0 ; i < 10 ; i++){ s.push_back(l + d / 10 * i); } s.push_back(r); s.resize(unique(s.begin(), s.end()) - s.begin()); int sz = (int)s.size() - 1; vector <ll> mnq, mxq; for(int i = 0 ; i < sz ; i++){ MinMax(s[i], s[i + 1], &mn, &mx); if(mn != -1){ mnq.push_back(mn); mxq.push_back(mx); } } if(mnq.size()){ ans = max(ans, mnq[0] - (l - 1)); ans = max(ans, r + 1 - mxq.back()); } else ans = max(ans, r + 1 - (l - 1)); for(int i = 0 ; i + 1 < (int)mnq.size() ; i++){ ans = max(ans, mnq[i + 1] - mxq[i]); } for(int i = 0 ; i < (int)mnq.size() ; i++){ solve(mnq[i] + 1, mxq[i] - 1); } } ll findGap(int T, int N){ if(T == 1){ MinMax(0, 1e18, &mn, &mx); ll ans = 0; while(mn + 1 < mx){ ll new_mn, new_mx; MinMax(mn + 1, mx - 1, &new_mn, &new_mx); ans = max(ans, new_mn - mn); ans = max(ans, new_mx - mx); mn = new_mn; mx = new_mx; } if(mn != mx) ans = max(ans, mx - mn); return ans; } MinMax(0, 1e18, &mn, &mx); solve(mn + 1, mx - 1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...