Submission #1209106

#TimeUsernameProblemLanguageResultExecution timeMemory
1209106basaSeesaw (JOI22_seesaw)C++20
0 / 100
0 ms400 KiB
#include "bits/stdc++.h"
#include <iomanip>

using namespace std;

#define int long long
#define ld long double

signed main()
{
  cin.tie(0) -> sync_with_stdio(0);
  int n;
  cin >> n;

  ld ldn = n;

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

  ld sum = 0;
  for(int i = 0; i < n; i++) sum += a[i];

  int lm = 0, rm = n - 1;
  ld l = sum / ldn, r = sum / ldn;
  array<ld, 3>mn = {(ld)LLONG_MAX, -1, 0};
  for(int i = 0; i < a[i]; i++){
    if(abs(a[i] - l) < mn[0]) mn = {abs(a[i] - l), (a[i] - l < 0 ? (ld)1 : (ld)0), a[i]};
  }

  if(mn[1] == 0) r = mn[2];
  else l = mn[2];

  if(l > r) swap(l, r);
  ldn--;
  for(int i = 0; i < n - 1; i++){
    ld curl = (sum - a[lm]) / ldn, curr = (sum - a[rm]) / ldn;

    // cout << curl << ' ' << curr << '\n';

    array<ld, 2>mn;
    mn[0] = LLONG_MAX;

    if(curl - r >= 0){
      mn[0] = curl - r;
      mn[1] = 0;
    }
    else{
      mn[0] = -1;
      mn[1] = 0;
    }

    if(l - curr >= 0){
      if(mn[0] > l - curr){
        mn[0] = l - curr;
        mn[1] = 1;
      }
    }
    else{
      mn[0] = -1;
      mn[1] = 1;
    }

    // cout << l << ' ' << r << ' ';
    if(mn[0] == -1){
      if(mn[1] == 0){
        // cout << a[lm] << '\n';
        sum -= a[lm];
        lm++;
      }
      else{
        // cout << a[rm] << '\n';
        sum -= a[rm];
        rm--;
      }
    }
    else if(mn[1] == 0){
      // cout << a[lm] << '\n';
      sum -= a[lm];
      lm++;
      r = curl;
    }
    else{
      // cout << a[rm] << '\n';
      sum -= a[rm];
      rm--;
      l = curr;
    }

    ldn--;
  }

  cout << fixed << setprecision(10) << r - l << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...