Submission #973346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
973346	2024-05-01T19:17:38 Z	IdanRosen	Mobile (BOI12_mobile)	C++	50 / 100	1000 ms	91900 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 < abs(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	348 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	7 ms	772 KB	Output is correct
2	Correct	10 ms	792 KB	Output is correct
3	Correct	5 ms	604 KB	Output is correct
4	Correct	9 ms	788 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1096 KB	Output is correct
2	Correct	20 ms	1312 KB	Output is correct
3	Correct	27 ms	1088 KB	Output is correct
4	Correct	11 ms	1148 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1140 KB	Output is correct
2	Correct	23 ms	1120 KB	Output is correct
3	Correct	25 ms	1096 KB	Output is correct
4	Correct	11 ms	1112 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1216 KB	Output is correct
2	Correct	24 ms	1108 KB	Output is correct
3	Correct	28 ms	1092 KB	Output is correct
4	Correct	10 ms	1136 KB	Output is correct
5	Correct	15 ms	1096 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	224 ms	10048 KB	Output is correct
2	Correct	531 ms	10172 KB	Output is correct
3	Correct	322 ms	6408 KB	Output is correct
4	Correct	158 ms	10888 KB	Output is correct
5	Correct	151 ms	6096 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	226 ms	10028 KB	Output is correct
2	Correct	187 ms	11504 KB	Output is correct
3	Correct	212 ms	11752 KB	Output is correct
4	Correct	176 ms	11592 KB	Output is correct
5	Correct	150 ms	12176 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	364 ms	10920 KB	Output is correct
2	Correct	503 ms	12064 KB	Output is correct
3	Correct	773 ms	11280 KB	Output is correct
4	Correct	116 ms	12672 KB	Output is correct
5	Correct	243 ms	12108 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	12016 KB	Output is correct
2	Correct	677 ms	11892 KB	Output is correct
3	Correct	879 ms	11636 KB	Output is correct
4	Correct	116 ms	13024 KB	Output is correct
5	Correct	253 ms	11660 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	439 ms	12316 KB	Output is correct
2	Correct	698 ms	13096 KB	Output is correct
3	Correct	896 ms	11880 KB	Output is correct
4	Correct	125 ms	12112 KB	Output is correct
5	Correct	234 ms	11620 KB	Output is correct

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1026 ms	50756 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	1020 ms	53012 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	1030 ms	72664 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	1044 ms	75476 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	1042 ms	75864 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	1088 ms	78984 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	1042 ms	78684 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	1098 ms	82992 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	1014 ms	86064 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	1064 ms	91900 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #973346

Compilation message