Submission #877822

#	Time	Username	Problem	Language	Result	Execution time	Memory
877822		frostray8653	Seesaw (JOI22_seesaw)	C++17	67 / 100	2063 ms	3456 KiB

seesaw

// #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 (stderr)

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 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 33