oj.uz

Submission #739886

# Submission time Handle Problem Language Result Execution time Memory
739886 2023-05-11T14:00:41 Z finn__ Seesaw (JOI22_seesaw) C++17
100 / 100
 59 ms 10016 KB 
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>

#define N 200001

int64_t a[N];
double e[N][2];

static inline int compare_centers(void const *const u, void const *const v)
{
    return *(double *)u < *(double *)v ? -1 : 1;
}

int main()
{
    size_t n;
    scanf("%zu", &n);
    for (size_t i = 1; i <= n; ++i)
        scanf("%" PRId64, a + i), a[i] += a[i - 1];
    for (size_t k = 0; k < n - 1; ++k)
    {
        size_t u = 1, v = n - k;
        double const y = (double)(k + 1) / n;
        while (u < v)
        {
            size_t const mid = (u + v) / 2;
            if ((a[mid + k] - a[mid - 1]) < (double)a[n] * y)
                u = mid + 1;
            else
                v = mid;
        }
        e[k][0] = (double)(a[u + k] - a[u - 1]) / (k + 1);
        e[k][1] = (double)(a[u + k - 1] - a[u - 2]) / (k + 1);
    }

    e[n - 1][0] = e[n - 1][1] = (double)a[n] / n;
    qsort(e, n, sizeof *e, compare_centers);
    double ans = 1e9, minl = (double)a[n] / n;

    for (size_t i = n - 1; i < n; --i)
    {
        ans = e[i][0] - minl < ans ? e[i][0] - minl : ans;
        minl = e[i][1] < minl ? e[i][1] : minl;
    }

    printf("%.10lf\n", ans);
}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%zu", &n);
      |     ~~~~~^~~~~~~~~~~
seesaw.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%" PRId64, a + i), a[i] += a[i - 1];
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 59 ms 10016 KB Output is correct
13 Correct 57 ms 9928 KB Output is correct
14 Correct 57 ms 10004 KB Output is correct
15 Correct 59 ms 10000 KB Output is correct
16 Correct 56 ms 9988 KB Output is correct