Submission #739886

#	Time	Username	Problem	Language	Result	Execution time	Memory
739886		finn__	Seesaw (JOI22_seesaw)	C++17	100 / 100	59 ms	10016 KiB

seesaw

#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 (stderr)

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 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33