oj.uz

Submission #973330

# Submission time Handle Problem Language Result Execution time Memory
973330 2024-05-01T18:38:21 Z IdanRosen Mobile (BOI12_mobile) C++
0 / 100
 1000 ms 82916 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ld> pld;

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

    ll n, l;
    cin >> n >> l;

    vector<pld> arr(n);
    for (auto &ref: arr) cin >> ref.first >> ref.second;

    ld start = 0;
    ld end = 1.42e9;
    while (end - start > 1e-6) {
        ld mid = start + (end - start) / 2;

        bool check = false;
        {
            vector<pld> ranges;
            for (int i = 0; i < n; i++) {
                if (mid < arr[i].second) continue;

                ld center = arr[i].first;
                ld delta = sqrt(mid * mid - (ld) (arr[i].second * arr[i].second));
                ranges.push_back({center - delta, center + delta});
            }

            if (ranges.empty()) {
                check = false;
            } else {

                std::sort(ranges.begin(), ranges.end());

                vector<pld> intersects;
                for (auto& range : ranges) {
                    if (intersects.empty())
                        intersects.push_back(range);
                    else {
                        if (range.first <= intersects.back().second) {
                            intersects.back().second = max(intersects.back().second, range.second);
                        } else
                            intersects.push_back(range);

                    }
                }

                for (auto& seg : intersects) {
                    if ((seg.first <= (ld) 0) && ((ld) l <= seg.second)) {
                        check = true;
                        break;
                    }
                }
            }
        }

        if (check)
            end = mid;
        else
            start = mid;
    }

    cout << fixed << setprecision(6) << start << endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1196 KB Output is correct
2 Correct 21 ms 1052 KB Output is correct
3 Correct 30 ms 1124 KB Output is correct
4 Incorrect 29 ms 1032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 10208 KB Output is correct
2 Correct 543 ms 10708 KB Output is correct
3 Correct 338 ms 5900 KB Output is correct
4 Incorrect 552 ms 10932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 9492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 11652 KB Output is correct
2 Correct 609 ms 11084 KB Output is correct
3 Correct 734 ms 9892 KB Output is correct
4 Incorrect 824 ms 10656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 11152 KB Output is correct
2 Correct 745 ms 11488 KB Output is correct
3 Correct 938 ms 11108 KB Output is correct
4 Incorrect 868 ms 10644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 11956 KB Output is correct
2 Correct 749 ms 11740 KB Output is correct
3 Correct 895 ms 10900 KB Output is correct
4 Incorrect 847 ms 10768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 48388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 49000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 69788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 68904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 72032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 72976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 75472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 76116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 82916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 81516 KB Time limit exceeded
2 Halted 0 ms 0 KB -