Submission #672959

#	Time	Username	Problem	Language	Result	Execution time	Memory
672959		MilosMilutinovic	Seesaw (JOI22_seesaw)	C++14	100 / 100	97 ms	17924 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<double> b(n);
  b[0] = a[0];
  for (int i = 1; i < n; i++) {
    b[i] = b[i - 1] + a[i];
  }
  auto Get = [&](int l, int r) {
    double s = b[r];
    if (l > 0) {
      s -= b[l - 1];
    }
    return s / (r - l + 1);
  };
  double c = Get(0, n - 1);
  vector<double> L(n);
  vector<double> R(n);
  for (int i = 1; i < n; i++) {
    {
      int l = 0, r = n - i, pos = -1;
      while (l <= r) {
        int mid = l + r >> 1;
        if (Get(mid, mid + i - 1) <= c) {
          pos = mid;
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      if (pos == -1) {
        L[i] = -1;
      } else {
        L[i] = Get(pos, pos + i - 1);
      }
    }
    {
      int l = 0, r = n - i, pos = -1;
      while (l <= r) {
        int mid = l + r >> 1;
        if (Get(mid, mid + i - 1) >= c) {
          pos = mid;
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      if (pos == -1) {
        R[i] = 2e9;
      } else {
        R[i] = Get(pos, pos + i - 1);
      }
    }
  }
//  for (int i = 1; i < n; i++) {
//    cout << fixed << setprecision(10) << L[i] << " " << R[i] << '\n';
//  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  order.erase(order.begin());
  sort(order.begin(), order.end(), [&](int i, int j) {
    return L[i] < L[j];
  });
  multiset<double> st;
  st.insert(c);
  double ans = c - *min_element(L.begin() + 1, L.end());
  for (int i : order) {
    ans = min(ans, *prev(st.end()) - L[i]);
    st.insert(R[i]);
  }
  ans = min(ans, *prev(st.end()) - c);
  cout << fixed << setprecision(10) << ans << '\n';
  return 0;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1;
      |                   ~~^~~
seesaw.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~

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