제출 #479580

#제출 시각아이디문제언어결과실행 시간메모리
479580HabitusGap (APIO16_gap)C++14
30 / 100
81 ms4112 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 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((maxi-mini+1LL)/((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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...