Submission #1270202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270202		os_bein_laggin	Mobile (BOI12_mobile)	C++20	50 / 100	1096 ms	31712 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

struct Interval {
    double l, r;
    bool operator<(const Interval &other) const {
        if (fabs(l - other.l) < 1e-12) return r < other.r;
        return l < other.l;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long L;
    cin >> N >> L;

    vector<pair<long long, long long> > stations(N);
    for (int i = 0; i < N; i++) {
        cin >> stations[i].first >> stations[i].second;
    }

    auto canCover = [&](double R) -> bool {
        vector<Interval> intervals;
        intervals.reserve(N);

        for (int i = 0; i < N; i++) {
            long long x = stations[i].first;
            long long y = stations[i].second;
            if (1.0 * y * y > R * R) continue; // cannot reach highway
            double dx = sqrt(R * R - 1.0 * y * y);
            double left = max(0.0, (double)x - dx);
            double right = min((double)L, (double)x + dx);
            if (left <= right) intervals.push_back(Interval{left, right});
        }

        if (intervals.empty()) return false;

        sort(intervals.begin(), intervals.end());

        double covered = 0.0;
        for (size_t i = 0; i < intervals.size(); i++) {
            if (intervals[i].l > covered + 1e-9) return false; // gap
            covered = max(covered, intervals[i].r);
            if (covered >= L) return true;
        }
        return false;
    };

    double lo = 0.0, hi = 2e9; // upper bound big enough
    for (int it = 0; it < 60; it++) {
        double mid = (lo + hi) / 2.0;
        if (canCover(mid)) hi = mid;
        else lo = mid;
    }

    cout << fixed << setprecision(6) << hi << "\n";
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5