Submission #576269

#	Time	Username	Problem	Language	Result	Execution time	Memory
576269		mmonteiro	Sure Bet (CEOI17_sure)	C++17	100 / 100	152 ms	3916 KiB

sure

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>

const double EPS = 1e-9;

int main(){

    int n;
    std::cin >> n;

    std::vector<double> a = {0.0}, b = {0.0};

    for(int i = 0; i < n; i++){
        double x, y;
        std::cin >> x >> y;
        a.push_back(x - 1.0);
        b.push_back(y - 1.0);
    }

    sort(a.rbegin(), a.rend() - 1);
    sort(b.rbegin(), b.rend() - 1);

    for(int i = 1; i <= n; ++i) {
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }

    double ans = 0.0;

    for(int k = 0; k < 2; ++k) {
        for(int i = 0; i <= n; ++i) {
            int lo = 1, hi = std::min(n, static_cast<int>(a[i])), best_j = 0;
            while(lo <= hi) {
                int j = (lo + hi) / 2;
                if( a[i] - j <= b[j] - i + EPS ) {
                    hi = j - 1;
                    best_j = j;
                } else {
                    lo = j + 1;
                }
            }
            ans = std::max(ans, std::min(a[i] - best_j, b[best_j] - i));
        }
        swap(a, b);
    }

    std::cout << std::fixed << std::setprecision(4) << ans << std::endl;

    return 0;
}

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