Submission #877822

#TimeUsernameProblemLanguageResultExecution timeMemory
877822frostray8653Seesaw (JOI22_seesaw)C++17
67 / 100
2063 ms3456 KiB
// #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];
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...