Submission #1127020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127020		VinhLuu	Seesaw (JOI22_seesaw)	C++20	100 / 100	366 ms	27300 KiB

seesaw

#include <bits/stdc++.h>
//#define ll long long

const int N = 1e6 + 5;

#define ll long double
using namespace std;

int n;
ll a[N];

//namespace sub1 {
//  void solve() {
//    cin >> n;
//    for(int i = 1; i <= n; i ++) cin >> a[i];
//    double ans = (double)(2e9);
//    for(int msk = 0; msk < (1 << n); msk ++) {
//      double sum = 0;
//      int l = 1, r = n;
//      for(int i = 1; i <= n; i ++) sum += a[i];
//      double cnt = n;
//      double mi = (1.0 * sum) / (1.0 * cnt);
//      double mx = (1.0 * sum) / (1.0 * cnt);
//
//      for(int k = 1; k < n; k ++) if(msk >> (k - 1) & 1) {
//        sum -= a[r];
//        cnt--;
//        mx = max(mx, (1.0 * sum) / (1.0 * cnt));
//        mi = min(mi, (1.0 * sum) / (1.0 * cnt));
//        r --;
//      } else {
//        sum -= a[l];
//        cnt--;
//        mx = max(mx, (1.0 * sum) / (1.0 * cnt));
//        mi = min(mi, (1.0 * sum) / (1.0 * cnt));
//        l ++;
//      }
//      ans = min(ans, mx - mi);
//    }
//    cout << setprecision(9) << fixed << ans;
//  }
//}

namespace AC {
  ll s[N];
  int L[N], R[N];
  ll cal(int l,int r) {
    return (ll)(s[r] - s[l - 1]) / (ll)(r - l + 1);
  }
  void solve() {
    ll sum = 0;
    for(int i = 1; i <= n; i ++) sum += a[i], s[i] = s[i - 1] + a[i];
    ll med = sum / n;

    multiset<ll> save;
    save.insert(med);

    int l[2], r[2];
    l[0] = 1, r[0] = n, l[1] = 1, r[1] = n;

    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

    for(int i = n - 1; i >= 1; i --) {
      set<pair<ll,ll>> tmp;
      tmp.insert({l[0] + 1, r[0]});
      tmp.insert({l[0], r[0] - 1});
      tmp.insert({l[1], r[1] - 1});
      tmp.insert({l[1] + 1, r[1]});
      int nl[2], nr[2];
      ll _left = (ll)2e9, _right = (ll)2e9;
      nl[0] = nl[1] = nr[0] = nr[1] = 0;
      for(auto [x, y] : tmp) {
        int val = cal(x, y);
        if(val <= med && med - val < _left) {
          _left = med - val;
          nl[0] = x, nr[0] = y;
        }
        if(val > med && val - med < _right) {
          _right = val - med;
          nl[1] = x, nr[1] = y;
        }
      }
      save.insert(cal(nl[0], nr[0]));
      if(nl[1] != nl[0] || nr[1] != nr[0]) {
        L[i] = nl[1], R[i] = nr[1];
        pq.push({cal(nl[0], nr[0]), i});
      }
      l[0] = nl[0], r[0] = nr[0], l[1] = nl[1], r[1] = nr[1];
    }

    ll ans = (ll)(2e9);

    ans = min(ans, (*save.rbegin()) - (*save.begin()));

    while(!pq.empty()) {
      ll w;
      int id; tie(w, id) = pq.top(); pq.pop();
      auto ptr = save.find(w);
      save.erase(w);
      save.insert(cal(L[id], R[id]));
      ans = min(ans, (*save.rbegin()) - (*save.begin()));
    }

    cout << setprecision(9) << fixed << ans;

  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "seesaw"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n;
  for(int i = 1; i <= n; i ++) cin >> a[i];
  AC :: solve();
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
seesaw.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33