제출 #479581

#제출 시각아이디문제언어결과실행 시간메모리
479581HabitusGap (APIO16_gap)C++14
30 / 100
77 ms4056 KiB
#include "gap.h" #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define dec(x, y) fixed << setprecision((y)) << (x) #define xx first #define yy second #define srt(v) sort((v).begin(), (v).end()) #define srtr(v) sort((v).rbegin(), (v).rend()) #define pb push_back #define popb pop_back #define sz(a) (int)(a).size() #define len(a) (int)(a).length() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const ll maks=(ll)1e18; /*ll b[100002]; int m; void MinMax(ll s, ll t, ll &mn, ll &mx) { int it=lower_bound(b, b+m, s)-b; int it1=lower_bound(b, b+m, t+1)-1-b; if(it1<it) {mn=mx=-1;} else {mn=b[it]; mx=b[it1];} }*/ ll findGap(int T, int N) { int n=N; if(T==1) { ll a[100002]; ll mini=0LL, maxi=maks+1LL; for(int i=0; i<(n+1)/2; ++i) { MinMax(mini+1, maxi-1, &mini, &maxi); a[i]=mini; a[n-i-1]=maxi; } maxi=0LL; for(int i=1; i<n; ++i) { maxi=max(maxi, a[i]-a[i-1]); } return maxi; } ll mini, maxi; MinMax(1LL, maks, &mini, &maxi); vector<ll> v; v.pb(mini); v.pb(maxi); ll x=ceil((double)(maxi-mini+1LL)/(double)((ll)n-1LL)); ll mn1, mx1; for(int i=0;; ++i) { if(mini+(ll)i*x>=maxi) break; MinMax((i==0?1LL:0LL)+mini+(ll)i*x, min(mini+(ll)(i+1)*x-1LL, maxi-1LL), &mn1, &mx1); v.pb(mn1); v.pb(mx1); } srt(v); maxi=0LL; for(int i=1; i<sz(v); ++i) { maxi=max(maxi, v[i]-v[i-1]); } return maxi; } /*int main() { cin >> m; for(int i=0; i<m; ++i) { cin >> b[i]; } cout << findGap(2, m); return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...