Submission #615327

#TimeUsernameProblemLanguageResultExecution timeMemory
615327wiwihoSeesaw (JOI22_seesaw)C++14
67 / 100
1376 ms1048576 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } struct Comp{ bool operator()(pll xc, pll yc){ return (__int128)xc.F * yc.S < (__int128)yc.F * xc.S; } }; void waassert(bool t){ if(t) return; cout << "WA\n"; exit(0); } int main(){ StarBurstStream int n; cin >> n; vector<ll> a(n + 1), s(n + 1); for(int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i]; auto getcen = [&](int l, int r){ return mp(s[r] - s[l - 1], r - l + 1); }; auto comp = [&](pll xc, pll yc){ return (__int128)xc.F * yc.S < (__int128)yc.F * xc.S; }; auto getdis = [&](pll x, pll y){ ld tx = (ld)x.F / x.S; ld ty = (ld)y.F / y.S; return abs(tx - ty); }; vector<pii> tmp; for(int i = 1; i <= n; i++){ for(int j = i; j <= n; j++) tmp.eb(mp(i, j)); } sort(iter(tmp), [&](pii x, pii y){ pll xc = getcen(x.F, x.S); pll yc = getcen(y.F, y.S); return comp(xc, yc); }); pll mid = getcen(1, n); vector<pii> good; vector<pii> lg(n + 1), rg(n + 1); lg[n] = rg[n] = mp(1, n); for(int i = 0; i < n - 1; i++){ { int l = 1, r = n - i; while(l < r){ int m = (l + r) / 2; if(comp(getcen(m, m + i), mid)) l = m + 1; else r = m; } rg[i + 1] = mp(l, l + i); } { int l = 1, r = n - i; while(l < r){ int m = (l + r + 1) / 2; if(comp(mid, getcen(m, m + i))) r = m - 1; else l = m; } good.eb(mp(l, l + i)); lg[i + 1] = mp(l, l + i); } } waassert(n <= 2000); /*printv(lg, cerr); printv(rg, cerr);*/ sort(iter(good), [&](pii x, pii y){ return comp(getcen(x.F, x.S), getcen(y.F, y.S)); }); reverse(iter(good)); multiset<pll, Comp> st; for(int i = 1; i <= n; i++){ st.insert(getcen(rg[i].F, rg[i].S)); } ld ans = getdis(*st.begin(), *st.rbegin()); /*cerr << "test "; printv(st, cerr);*/ for(pll i : good){ int len = i.S - i.F + 1; auto it = st.find(getcen(rg[len].F, rg[len].S)); st.erase(it); st.insert(getcen(i.F, i.S)); /*cerr << "test " << i << " : "; printv(st, cerr);*/ ans = min(ans, getdis(*st.begin(), *st.rbegin())); } cout << fixed << setprecision(20) << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...