oj.uz

Submission #1057220

# Submission time Handle Problem Language Result Execution time Memory
1057220 2024-08-13T15:32:53 Z juicy Seesaw (JOI22_seesaw) C++17
100 / 100
 55 ms 15568 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n;
int a[N], fre[N];
long long pf[N];

double qry(int l, int r) {
  return (double) (pf[r] - pf[l - 1]) / (r - l + 1);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pf[i] = pf[i - 1] + a[i];
  }
  double A = qry(1, n);
  vector<pair<double, int>> cands = {{A, n}};
  for (int l = 1; l < n; ++l) {
    int L = 1, R = n - l + 1, p = 0;
    while (L <= R) {
      int md = (L + R) / 2; 
      if (qry(md, md + l - 1) < A) {
        p = md;
        L = md + 1;
      } else {
        R = md - 1;
      }
    }
    cands.push_back({qry(p, p + l - 1), l});
    cands.push_back({qry(p + 1, p + l), l});
  }
  sort(cands.begin(), cands.end());
  double res = 1e9;
  for (int i = 0, j = 0, cnt = 0; i < cands.size(); ++i) {
    while (j < cands.size() && cnt < n) {
      cnt += !fre[cands[j++].second]++;
    }
    if (cnt == n) {
      res = min(res, cands[j - 1].first - cands[i].first);
    }
    cnt -= !--fre[cands[i].second];
  }
  cout << fixed << setprecision(12) << res;
  return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:47:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0, j = 0, cnt = 0; i < cands.size(); ++i) {
      |                                   ~~^~~~~~~~~~~~~~
seesaw.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (j < cands.size() && cnt < n) {
      |            ~~^~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 49 ms 15568 KB Output is correct
13 Correct 48 ms 15056 KB Output is correct
14 Correct 48 ms 15560 KB Output is correct
15 Correct 55 ms 14540 KB Output is correct
16 Correct 48 ms 14288 KB Output is correct