Submission #973336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
973336	2024-05-01T18:53:48 Z	IdanRosen	Mobile (BOI12_mobile)	C++	60 / 100	1000 ms	83028 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) / 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.emplace_back(center - delta, center + delta);
            }

//            std::sort(ranges.begin(), ranges.end(), [](const pld& left, const pld& right) -> bool {
//                return left.first < right.first;
//            });

            ld curr_len = 0;
            for (auto &range: ranges) {
                if (range.first <= curr_len) {
                    curr_len = max(curr_len, range.second);
                }
            }

           if (curr_len >= (ld) l)
               check = true;
           else
               check = false;

        }

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

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

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	600 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1024 KB	Output is correct
2	Correct	5 ms	792 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	4 ms	788 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1032 KB	Output is correct
2	Correct	11 ms	1108 KB	Output is correct
3	Correct	9 ms	1244 KB	Output is correct
4	Correct	8 ms	1120 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1056 KB	Output is correct
2	Correct	10 ms	1120 KB	Output is correct
3	Correct	7 ms	1088 KB	Output is correct
4	Correct	9 ms	1120 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1192 KB	Output is correct
2	Correct	10 ms	1048 KB	Output is correct
3	Correct	7 ms	1036 KB	Output is correct
4	Correct	8 ms	1032 KB	Output is correct
5	Correct	8 ms	1072 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	10152 KB	Output is correct
2	Correct	200 ms	10868 KB	Output is correct
3	Correct	104 ms	5904 KB	Output is correct
4	Correct	126 ms	10584 KB	Output is correct
5	Correct	84 ms	6112 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	10072 KB	Output is correct
2	Correct	125 ms	11596 KB	Output is correct
3	Correct	136 ms	11752 KB	Output is correct
4	Correct	131 ms	12360 KB	Output is correct
5	Correct	136 ms	11444 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	220 ms	11664 KB	Output is correct
2	Correct	179 ms	9900 KB	Output is correct
3	Correct	102 ms	11380 KB	Output is correct
4	Correct	156 ms	11036 KB	Output is correct
5	Correct	146 ms	11160 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	10936 KB	Output is correct
2	Correct	169 ms	11820 KB	Output is correct
3	Correct	191 ms	11868 KB	Output is correct
4	Correct	171 ms	10588 KB	Output is correct
5	Correct	154 ms	12124 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	211 ms	10884 KB	Output is correct
2	Correct	216 ms	11084 KB	Output is correct
3	Correct	186 ms	11372 KB	Output is correct
4	Correct	153 ms	10828 KB	Output is correct
5	Correct	159 ms	12456 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	925 ms	48432 KB	Output is correct
2	Correct	949 ms	56396 KB	Output is correct
3	Correct	971 ms	55348 KB	Output is correct
4	Correct	822 ms	58192 KB	Output is correct
5	Correct	834 ms	54796 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	939 ms	48428 KB	Output is correct
2	Correct	738 ms	55108 KB	Output is correct
3	Correct	849 ms	53684 KB	Output is correct
4	Correct	792 ms	57344 KB	Output is correct
5	Correct	777 ms	55048 KB	Output is correct

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1101 ms	69732 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	1035 ms	70036 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	1064 ms	72756 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	1033 ms	71748 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	1031 ms	76192 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	1040 ms	76532 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	1059 ms	83028 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	1022 ms	81856 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #973336

Compilation message