제출 #1286666

#제출 시각아이디문제언어결과실행 시간메모리
1286666samarthkulkarniMobile (BOI12_mobile)C++20
컴파일 에러
0 ms0 KiB
void solution() {
    ll N;
    ld L;
    cin >> N >> L;

    vector<pair<ld, ld>> a(N);
    for (int i = 0; i < N; i++) {
        ld x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }

    // This function now correctly returns 'true' if the highway is FULLY COVERED.
    auto isCovered = [&](ld d) {
        vector<pair<ld, ld>> intervals;
        ld d_squared = d * d;

        // --- BUG FIX #1: Correctly handle stations that can't reach ---
        for (int i = 0; i < N; i++) {
            if (d < abs(a[i].ss)) {
                continue; // Skip stations that are too far from the highway.
            }
            
            ld radius_on_highway = sqrt(d_squared - a[i].ss * a[i].ss);
            ld p = max((ld)0.0, a[i].ff - radius_on_highway);
            ld q = min(L, a[i].ff + radius_on_highway);

            if (p <= q) {
                 intervals.push_back({p, q});
            }
        }

        if (intervals.empty()) {
            return L <= 1e-9; // Covered only if highway length is effectively zero.
        }

        sort(all(intervals));

        // --- BUG FIX #2: Robust greedy interval merging logic ---
        ld coverage_end = 0.0;
        if (intervals[0].ff > 1e-9) {
            return false; // Gap at the very start of the highway.
        }

        ld max_reach_this_step = 0.0;
        int i = 0;
        while (coverage_end < L) {
            // Find the furthest reachable point from all intervals that start within our current coverage.
            while (i < intervals.size() && intervals[i].ff <= coverage_end + 1e-9) {
                max_reach_this_step = max(max_reach_this_step, intervals[i].ss);
                i++;
            }

            // If we couldn't extend our coverage, it means there's a gap.
            if (max_reach_this_step <= coverage_end) {
                return false;
            }
            
            coverage_end = max_reach_this_step;
        }

        return true; // If the loop completes, the highway is fully covered.
    };

    // --- BUG FIX #3: Correct binary search for the MINIMUM passing value ---
    ld p = 0, q = 2e9; // A safe upper bound
    
    // We run for a fixed number of iterations to guarantee precision.
    for(int i = 0; i < 100; ++i) { 
        ld mid = p + (q - p) / 2;
        if (isCovered(mid)) {
            // 'mid' works. Let's try for an even SMALLER radius.
            q = mid;
        } else {
            // 'mid' failed. We MUST use a LARGER radius.
            p = mid;
        }
    }

    // The answer is 'q', the smallest value for which isCovered(q) was true.
    cout << fixed << setprecision(10) << q << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

mobile.cpp: In function 'void solution()':
mobile.cpp:2:5: error: 'll' was not declared in this scope
    2 |     ll N;
      |     ^~
mobile.cpp:3:5: error: 'ld' was not declared in this scope
    3 |     ld L;
      |     ^~
mobile.cpp:4:5: error: 'cin' was not declared in this scope
    4 |     cin >> N >> L;
      |     ^~~
mobile.cpp:4:12: error: 'N' was not declared in this scope
    4 |     cin >> N >> L;
      |            ^
mobile.cpp:4:17: error: 'L' was not declared in this scope
    4 |     cin >> N >> L;
      |                 ^
mobile.cpp:6:12: error: 'pair' was not declared in this scope
    6 |     vector<pair<ld, ld>> a(N);
      |            ^~~~
mobile.cpp:6:5: error: 'vector' was not declared in this scope
    6 |     vector<pair<ld, ld>> a(N);
      |     ^~~~~~
mobile.cpp:6:26: error: 'a' was not declared in this scope
    6 |     vector<pair<ld, ld>> a(N);
      |                          ^
mobile.cpp:8:11: error: expected ';' before 'x'
    8 |         ld x, y;
      |           ^~
      |           ;
mobile.cpp:9:16: error: 'x' was not declared in this scope
    9 |         cin >> x >> y;
      |                ^
mobile.cpp:9:21: error: 'y' was not declared in this scope
    9 |         cin >> x >> y;
      |                     ^
mobile.cpp:14:26: error: 'ld' is not a type
   14 |     auto isCovered = [&](ld d) {
      |                          ^~
mobile.cpp: In lambda function:
mobile.cpp:15:30: error: 'intervals' was not declared in this scope
   15 |         vector<pair<ld, ld>> intervals;
      |                              ^~~~~~~~~
mobile.cpp:20:21: error: 'abs' was not declared in this scope
   20 |             if (d < abs(a[i].ss)) {
      |                     ^~~
mobile.cpp:28:17: error: 'p' was not declared in this scope
   28 |             if (p <= q) {
      |                 ^
mobile.cpp:28:22: error: 'q' was not declared in this scope
   28 |             if (p <= q) {
      |                      ^
mobile.cpp:37:14: error: 'all' was not declared in this scope
   37 |         sort(all(intervals));
      |              ^~~
mobile.cpp:37:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   37 |         sort(all(intervals));
      |         ^~~~
      |         short
mobile.cpp:47:16: error: 'coverage_end' was not declared in this scope
   47 |         while (coverage_end < L) {
      |                ^~~~~~~~~~~~
mobile.cpp:50:17: error: 'max_reach_this_step' was not declared in this scope
   50 |                 max_reach_this_step = max(max_reach_this_step, intervals[i].ss);
      |                 ^~~~~~~~~~~~~~~~~~~
mobile.cpp:50:39: error: 'max' was not declared in this scope
   50 |                 max_reach_this_step = max(max_reach_this_step, intervals[i].ss);
      |                                       ^~~
mobile.cpp:55:17: error: 'max_reach_this_step' was not declared in this scope
   55 |             if (max_reach_this_step <= coverage_end) {
      |                 ^~~~~~~~~~~~~~~~~~~
mobile.cpp:59:28: error: 'max_reach_this_step' was not declared in this scope
   59 |             coverage_end = max_reach_this_step;
      |                            ^~~~~~~~~~~~~~~~~~~
mobile.cpp: In function 'void solution()':
mobile.cpp:66:7: error: expected ';' before 'p'
   66 |     ld p = 0, q = 2e9; // A safe upper bound
      |       ^~
      |       ;
mobile.cpp:70:11: error: expected ';' before 'mid'
   70 |         ld mid = p + (q - p) / 2;
      |           ^~~~
      |           ;
mobile.cpp:71:23: error: 'mid' was not declared in this scope
   71 |         if (isCovered(mid)) {
      |                       ^~~
mobile.cpp:73:13: error: 'q' was not declared in this scope
   73 |             q = mid;
      |             ^
mobile.cpp:76:13: error: 'p' was not declared in this scope
   76 |             p = mid;
      |             ^
mobile.cpp:81:5: error: 'cout' was not declared in this scope
   81 |     cout << fixed << setprecision(10) << q << endl;
      |     ^~~~
mobile.cpp:81:13: error: 'fixed' was not declared in this scope
   81 |     cout << fixed << setprecision(10) << q << endl;
      |             ^~~~~
mobile.cpp:81:22: error: 'setprecision' was not declared in this scope
   81 |     cout << fixed << setprecision(10) << q << endl;
      |                      ^~~~~~~~~~~~
mobile.cpp:81:42: error: 'q' was not declared in this scope
   81 |     cout << fixed << setprecision(10) << q << endl;
      |                                          ^
mobile.cpp:81:47: error: 'endl' was not declared in this scope
   81 |     cout << fixed << setprecision(10) << q << endl;
      |                                               ^~~~