oj.uz

Submission #910949

# Submission time Handle Problem Language Result Execution time Memory
910949 2024-01-18T10:10:42 Z cig32 Seesaw (JOI22_seesaw) C++17
67 / 100
 939 ms 1048576 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
}
void solve(int tc) { 
  int n;
  cin >> n;
  int a[n+1];
  for(int i=1; i<=n; i++) {
    cin >> a[i];
  }
  sort(a+1, a+n+1);
  int ps[n+1];
  ps[0] = 0;
  for(int i=1; i<=n; i++) ps[i] = ps[i-1] + a[i];
  vector<pair<double,int>>v;
  for(int l=1; l<=n; l++) {
    for(int r=l; r<=n; r++) {
      v.push_back({(ps[r] - ps[l-1]) * 1.0 / (r - l + 1), r - l + 1});
    }
  }
  sort(v.begin(), v.end());
  int freq[n+1];
  for(int i=1; i<=n; i++) freq[i] = 0;
  int s = 0, j = -1;
  double ans = 1e9;
  for(int i=0; i<v.size(); i++) {
    if(i > 0) {
      int bruh = v[i-1].second;
      freq[bruh]--;
      if(!freq[bruh]) s--;
    }
    j = max(j, i-1);
    while(s < n && j+1 < v.size()) {
      j++;
      int bruh = v[j].second;
      freq[bruh]++;
      if(freq[bruh] == 1) s++;
    }
    if(s == n) ans = min(ans, v[j].first - v[i].first);
  }
  cout << fixed << setprecision(10) << ans << '\n';
}

void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ A.cpp -std=c++17 -O2 -o A
./A < input.txt
*/

Compilation message

seesaw.cpp: In function 'void solve(long long int)':
seesaw.cpp:60:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
seesaw.cpp:67:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(s < n && j+1 < v.size()) {
      |                    ~~~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 1 ms 736 KB Output is correct
6 Correct 2 ms 872 KB Output is correct
7 Correct 2 ms 872 KB Output is correct
8 Correct 336 ms 67288 KB Output is correct
9 Correct 346 ms 68032 KB Output is correct
10 Correct 367 ms 67016 KB Output is correct
11 Correct 361 ms 68032 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 864 KB Output is correct
5 Correct 1 ms 736 KB Output is correct
6 Correct 2 ms 872 KB Output is correct
7 Correct 2 ms 872 KB Output is correct
8 Correct 336 ms 67288 KB Output is correct
9 Correct 346 ms 68032 KB Output is correct
10 Correct 367 ms 67016 KB Output is correct
11 Correct 361 ms 68032 KB Output is correct
12 Runtime error 939 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -