Submission #1127081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127081		duckindog	Seesaw (JOI22_seesaw)	C++20	100 / 100	960 ms	31512 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define double long double

const int N = 600'000 + 10;
const double MAX = 1e9;

int n;
int a[N];
long long pref[N];
inline long long sum(int l, int r) { return pref[r] - pref[l - 1]; }
inline double cal(int l, int r) { return (double)sum(l, r) / (r - l + 1); }

const int dx[] = {0, 1}, dy[] = {-1, 0};
bool mk[N];
int way[N];
int par[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];

  for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];

  vector<pair<int, int>> nodes;
  double med = cal(1, n);
  nodes.push_back({1, n});
  vector<pair<int, int>> curNode = {{1, n}};
  for (int size = n; size > 1; --size) { 
    vector<pair<int, int>> nxtNode;
    for (const auto& [l, r] : curNode) 
      nxtNode.push_back({l + 1, r}), nxtNode.push_back({l, r - 1});
    sort(nxtNode.begin(), nxtNode.end());
    nxtNode.erase(unique(nxtNode.begin(), nxtNode.end()), nxtNode.end());
    
    sort(nxtNode.begin(), nxtNode.end(), [&](const auto& a, const auto& b) { 
      return abs(cal(a.first, a.second) - med) < abs(cal(b.first, b.second) - med);
    });
    while (nxtNode.size() > 3) nxtNode.pop_back();
    curNode = nxtNode;

    nodes.insert(nodes.end(), nxtNode.begin(), nxtNode.end());
  }
  
  sort(nodes.begin(), nodes.end());
  nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

  using TP = tuple<double, int>;
  priority_queue<TP, vector<TP>, greater<>> q;
  
  multiset<double> s;
  double answer = MAX;
  auto go = [&](int idx) { 
    for (;;) { 
      const auto& [x, y] = nodes[idx];
      
      if (x == y) break;
      if (!mk[idx]) s.insert(cal(x, y)), q.emplace(cal(x, y), idx), mk[idx] = true;

      int nX = x + dx[way[idx]], nY = y + dy[way[idx]];
      if (!binary_search(nodes.begin(), nodes.end(), make_pair(nX, nY))) { 
        way[idx] = 1;
        nX = x + dx[way[idx]], nY = y + dy[way[idx]];
      }
      if (!binary_search(nodes.begin(), nodes.end(), make_pair(nX, nY))) break;

      int nIdx = lower_bound(nodes.begin(), nodes.end(), make_pair(nX, nY)) - nodes.begin();
      par[nIdx] = idx;
      idx = nIdx;
      
      if (mk[idx]) break;
    } 
    const auto& [x, y] = nodes[idx];
    if (!mk[idx]) s.insert(cal(x, y)), q.emplace(cal(x, y), idx), mk[idx] = true;
    
    if ((int)s.size() == n) answer = min(answer, *s.rbegin() - *s.begin());
  };

  go(lower_bound(nodes.begin(), nodes.end(), make_pair(1, n)) - nodes.begin());
  while (q.size()) { 
    auto [d, idx] = q.top(); q.pop();
    if (nodes[idx].first == 1 && nodes[idx].second == n)  continue;
    s.extract(d);
    int pIdx = par[idx];
    if (way[pIdx]) continue;
    way[pIdx] = 1;
    go(pIdx);
  }

  cout << setprecision(9) << fixed << answer << "\n";
}

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