Submission #973329

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
973329	2024-05-01T18:37:04 Z	IdanRosen	Mobile (BOI12_mobile)	C++	0 / 100	1000 ms	82204 KB

mobile

#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 (int i = 0; i < n; i++) {
                    if (intersects.empty())
                        intersects.push_back(ranges[i]);
                    else {
                        if (ranges[i].first <= intersects.back().second) {
                            intersects.back().second = max(intersects.back().second, ranges[i].second);
                        } else
                            intersects.push_back(ranges[i]);

                    }
                }

                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	1 ms	348 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	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	1188 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	1288 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	1044 KB	Output is correct
2	Correct	22 ms	1208 KB	Output is correct
3	Correct	30 ms	1036 KB	Output is correct
4	Incorrect	30 ms	1284 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	180 ms	12968 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	247 ms	13132 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	445 ms	10896 KB	Output is correct
2	Correct	567 ms	9908 KB	Output is correct
3	Runtime error	162 ms	13700 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	563 ms	10864 KB	Output is correct
2	Correct	732 ms	11556 KB	Output is correct
3	Runtime error	207 ms	13500 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	495 ms	11044 KB	Output is correct
2	Correct	783 ms	11944 KB	Output is correct
3	Runtime error	218 ms	13364 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1029 ms	48192 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	1036 ms	48408 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	1065 ms	69532 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	1027 ms	70364 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	1077 ms	72964 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	1049 ms	72512 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	1044 ms	76056 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	1026 ms	75016 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	1052 ms	81132 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	1051 ms	82204 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #973329

Compilation message