Submission #802018

#	Time	Username	Problem	Language	Result	Execution time	Memory
802018		hat0412	Sure Bet (CEOI17_sure)	C++14	100 / 100	135 ms	5196 KiB

sure

#include <bits/stdc++.h>

#define lli long long
#define lld long double
#define pb push_back
#define fi first
#define se second
#define name "surebet"

using namespace std;

const int N = 1e5 + 10;
const lld esp = 1e-6;

int n;
long double a[N], b[N];

bool cmp (long double a, long double b)
{
    return a > b;
}

void read()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        a[i] -= 1.0; b[i] -= 1.0;
    }

    sort(a + 1, a + 1 + n, cmp);
    sort(b + 1, b + 1 + n, cmp);
}

void sub1()
{
    lld res = 0, tmp1 = 0, tmp2 = 0;
    for (int i = 0; i <= n; i++)
    {
        tmp1 += a[i]; tmp2 = 0;
        for (int j = 0; j <= n; j++)
        {
            tmp2 += b[j];
            res = max(res, min(tmp1 - j, tmp2 - i));
        }
    }
    cout << fixed << setprecision(4) << res;
}

lld Cal (int i, int j)
{
    return min(a[i] - j, b[j] - i);
}

int Find (int i)
{
    int l = 0, r = n;
    while (l < r - 1)
    {
        int m = (l + r) >> 1;
        int mm = (m + r) >> 1;
        if (Cal(i, m) - Cal(i, mm) > esp) r = mm;
        else l = m;
    }
    if (Cal(i, l) > Cal(i, r)) return l;
    return r;
}

void sub2()
{
    lld res = 0;
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    for (int i = 1; i <= n; i++) b[i] += b[i - 1];
    for (int i = 0; i <= n; i++)
    {
        int j = Find(i);
        res = max(res, Cal(i, j));
    }
    cout << fixed << setprecision(4) << res;
}

void solve()
{
    if (n <= 1000) {sub1(); return;}
    sub2();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }

    read();
    solve();
}

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sure.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40