oj.uz

Submission #866894

# Submission time Handle Problem Language Result Execution time Memory
866894 2023-10-27T09:44:53 Z sleepntsheep Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 2396 KB 
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

int n;
ld a[N], b[N];

int ok(ld x)
{
    for (int take = 0; take <= 2*n; ++take)
    {
        int l = n-take, r = n-1, L=-1, R=-1;
        while (l <= r)
        {
            int y = (l+r)/2;
            if (a[y] - take >= x) l=y+1, L=y;
            else r=y-1;
        }
        if (L==-1) continue;
        l=n-take-(n-L), r = n-1;
        while (l <= r)
        {
            int y = (l+r)/2;
            if (b[y] - take >= x) l=y+1, R=y;
            else r=y-1;
        }
        if (R != -1 && 2*n-L-R <= take) return 1;
    }
    return 0;
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    sort(a, a+n), sort(b, b+n);
    for (int i = n; i--;) a[i] += a[i+1], b[i] += b[i+1];

    ld l = 0, r = 1e9, iter=200;
    for (; --iter;)
    {
        ld y = (l+r)/2;
        if (ok(y)) l = y;
        else r = y;
    }
    cout << fixed << setprecision(4) << l;

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -