oj.uz

Submission #910952

# Submission time Handle Problem Language Result Execution time Memory
910952 2024-01-18T10:13:59 Z cig32 Seesaw (JOI22_seesaw) C++17
100 / 100
 382 ms 74044 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 len=1; len<=n; len++) {
    int lb = 1, rb = n-len+1;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      double bruh = (ps[mid+len-1] - ps[mid-1]) * 1.0 / len;
      if(bruh >= ps[n] * 1.0 / n) rb = mid;
      else lb = mid + 1;
    }
    for(int j=max(1ll, lb - 4); j<=min(n-len+1, lb + 4); j++) {
      double bruh = (ps[j+len-1] - ps[j-1]) * 1.0 / len;
      v.push_back({bruh, len});
    }
  }
  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:68: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]
   68 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
seesaw.cpp:75: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]
   75 |     while(s < n && j+1 < v.size()) {
      |                    ~~~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 1500 KB Output is correct
9 Correct 5 ms 1500 KB Output is correct
10 Correct 5 ms 1500 KB Output is correct
11 Correct 5 ms 1496 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 1500 KB Output is correct
9 Correct 5 ms 1500 KB Output is correct
10 Correct 5 ms 1500 KB Output is correct
11 Correct 5 ms 1496 KB Output is correct
12 Correct 378 ms 74044 KB Output is correct
13 Correct 382 ms 73904 KB Output is correct
14 Correct 367 ms 72012 KB Output is correct
15 Correct 356 ms 74008 KB Output is correct
16 Correct 381 ms 71976 KB Output is correct