Submission #933384

#TimeUsernameProblemLanguageResultExecution timeMemory
933384SmuggingSpunGap (APIO16_gap)C++14
30 / 100
33 ms3760 KiB
#include "gap.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T>void maximize(T& a, T b){ if(a < b){ a = b; } } long long findGap(int T, int n){ if(T == 1){ vector<ll>a(n); ll ans = 0, low = 0, high = 1e18; int l = 0, r = n - 1; while(l <= r){ MinMax(low, high, &a[l], &a[r]); low = a[l++] + 1; high = a[r--] - 1; } for(int i = 1; i < n; i++){ maximize(ans, a[i] - a[i - 1]); } return ans; } ll a_1, a_n; MinMax(0, 1e18, &a_1, &a_n); ll average = (a_n - a_1 + n - 2) / (n - 1), ans = average; for(ll i = a_1; i <= a_n; i += average + 1){ ll x, y; MinMax(i, min(i + average, a_1), &x, &y); if(x != -1){ maximize(ans, x - a_1); a_1 = y; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...