oj.uz

Submission #877822

# Submission time Handle Problem Language Result Execution time Memory
877822 2023-11-23T15:56:29 Z frostray8653 Seesaw (JOI22_seesaw) C++17
67 / 100
 2000 ms 3456 KB 
// #pragma GCC optimize("Ofast,unroll-loops,O3")
#include <bits/stdc++.h>
#define int long long
// #define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
using namespace std;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << " "; dbg(b...);}
void ent() {cout << "\n";}

const int mod = 998244353;
// const int mod = 1e9 + 7;
// const int INF = 2e9;
const int INF = 1e18;

/// ------- Initialization End -------

const int N = 200005;
int a[N], pre[N];

double enumerate(int l, int r, double mn, double mx) {
    if (l == r)
        return mx - mn;
    double lres = (double)(pre[r] - pre[l]) / (r - l);
    if (lres <= mx) { /// 取左邊的
        int ql = l + 1, qr = r;
        while (ql + 1 < qr) {
            int mid = (ql + qr) >> 1;
            if ((double)(pre[r] - pre[mid - 1]) / (r - mid + 1) <= mx)
                ql = mid;
            else
                qr = mid;
        }
        return enumerate(ql, r, mn, mx);
    }
    double rres = (double)(pre[r - 1] - pre[l - 1]) / (r - l);
    if (rres >= mn) { /// 取右邊的
        return enumerate(l, r - 1, mn, mx);
    }
    return min(enumerate(l + 1, r, mn, lres), enumerate(l, r - 1, rres, mx));
}

signed main() {
    IO;
    
    int n;
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    double tot = 0;
    FOR(i, 1, n) tot += a[i];
    double ave = tot / n;
    FOR(i, 1, n) pre[i] = pre[i - 1] + a[i];
    double ans = enumerate(1, n, ave, ave);
    cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:52:5: note: in expansion of macro 'FOR'
   52 |     FOR(i, 1, n) cin >> a[i];
      |     ^~~
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:54:5: note: in expansion of macro 'FOR'
   54 |     FOR(i, 1, n) tot += a[i];
      |     ^~~
seesaw.cpp:8:38: warning: unused variable 'I' [-Wunused-variable]
    8 | #define FOR(i, a, b) for (int i = a, I = b; i <= b; i++)
      |                                      ^
seesaw.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i, 1, n) pre[i] = pre[i - 1] + a[i];
      |     ^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1464 ms 2508 KB Output is correct
9 Correct 10 ms 2396 KB Output is correct
10 Correct 17 ms 2516 KB Output is correct
11 Correct 876 ms 2508 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1464 ms 2508 KB Output is correct
9 Correct 10 ms 2396 KB Output is correct
10 Correct 17 ms 2516 KB Output is correct
11 Correct 876 ms 2508 KB Output is correct
12 Execution timed out 2063 ms 3456 KB Time limit exceeded
13 Halted 0 ms 0 KB -