답안 #1113952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113952	2024-11-17T22:22:59 Z	slycelote	Mobile (BOI12_mobile)	C++17	75 / 100	1000 ms	44356 KB

mobile

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(0); iostream::sync_with_stdio(false);

    int n;
    long double d;
    cin >> n >> d;
    vector<long double> x, y;
    x.reserve(n); y.reserve(n);
    while (n--) {
        long double xx, yy; cin >> xx >> yy;
        yy = fabs(yy);
        if (!x.empty() && x.back() == xx) {
            y.back() = min(y.back(), yy);
        } else {
            x.push_back(xx);
            y.push_back(yy);
        }
    }
    n = x.size();
    long double L = 0, R = 4e9;
    while (R - L > 1e-4) {
        long double M = (L + R) / 2;
        vector<pair<long double, long double>> segs;
        for (int i = 0; i < n; ++i) if (M > y[i]) {
            long double len = sqrt(M*M - y[i]*y[i]);
            long double start = max((long double)0.0, x[i] - len), end = min(d, x[i] + len);
            if (start > end) {
                continue;
            }
            while (!segs.empty() && start < segs.back().second) {
                start = min(start, segs.back().first);
                end = max(end, segs.back().second);
                segs.pop_back();
            }
            segs.push_back({start, end});
        }
        if (segs.empty() || segs.size() > 1 || segs.back().first > 0 || segs.back().second < d) {
            L = M;
        } else {
            R = M;
        }
    }

    cout.precision(20);
    cout << (L+R)/2 << endl;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	336 KB	Output is correct
2	Correct	6 ms	336 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	3 ms	336 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	548 KB	Output is correct
2	Correct	7 ms	592 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	336 KB	Output is correct
2	Correct	8 ms	628 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	592 KB	Output is correct
2	Correct	7 ms	592 KB	Output is correct
3	Correct	3 ms	336 KB	Output is correct
4	Correct	6 ms	592 KB	Output is correct
5	Correct	3 ms	336 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	2384 KB	Output is correct
2	Correct	89 ms	2128 KB	Output is correct
3	Correct	66 ms	2640 KB	Output is correct
4	Correct	54 ms	4176 KB	Output is correct
5	Correct	13 ms	848 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	592 KB	Output is correct
2	Correct	40 ms	1360 KB	Output is correct
3	Correct	57 ms	2524 KB	Output is correct
4	Correct	59 ms	3912 KB	Output is correct
5	Correct	60 ms	4432 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	114 ms	3144 KB	Output is correct
2	Correct	80 ms	2092 KB	Output is correct
3	Correct	109 ms	3556 KB	Output is correct
4	Correct	62 ms	5448 KB	Output is correct
5	Correct	39 ms	2128 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	74 ms	1736 KB	Output is correct
2	Correct	73 ms	3032 KB	Output is correct
3	Correct	40 ms	1736 KB	Output is correct
4	Correct	62 ms	5448 KB	Output is correct
5	Correct	71 ms	4256 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	126 ms	3420 KB	Output is correct
2	Correct	72 ms	3016 KB	Output is correct
3	Correct	38 ms	1864 KB	Output is correct
4	Correct	60 ms	5532 KB	Output is correct
5	Correct	68 ms	4180 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	841 ms	15944 KB	Output is correct
2	Correct	154 ms	12104 KB	Output is correct
3	Correct	167 ms	11716 KB	Output is correct
4	Correct	334 ms	25672 KB	Output is correct
5	Correct	371 ms	19528 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	150 ms	4432 KB	Output is correct
2	Correct	702 ms	22468 KB	Output is correct
3	Correct	283 ms	10056 KB	Output is correct
4	Correct	351 ms	25416 KB	Output is correct
5	Correct	419 ms	21844 KB	Output is correct

Subtask #14
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1057 ms	19168 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	191 ms	4432 KB	Output is correct
2	Correct	717 ms	27060 KB	Output is correct
3	Correct	248 ms	11336 KB	Output is correct
4	Correct	390 ms	30800 KB	Output is correct
5	Correct	497 ms	25672 KB	Output is correct

Subtask #16
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1041 ms	22344 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	219 ms	4432 KB	Output is correct
2	Correct	833 ms	31168 KB	Output is correct
3	Correct	351 ms	12932 KB	Output is correct
4	Correct	479 ms	35524 KB	Output is correct
5	Correct	555 ms	31048 KB	Output is correct

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1054 ms	25312 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	4564 KB	Output is correct
2	Correct	907 ms	35656 KB	Output is correct
3	Correct	378 ms	14072 KB	Output is correct
4	Correct	550 ms	40936 KB	Output is correct
5	Correct	609 ms	36652 KB	Output is correct

Subtask #20
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1061 ms	31816 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	284 ms	4432 KB	Output is correct
2	Execution timed out	1083 ms	44356 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

답안 #1113952

Compilation message