Submission #464195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
464195	2021-08-12T13:38:04 Z	dqk	Mobile (BOI12_mobile)	C++17	65 / 100	659 ms	55060 KB

mobile

#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    double L;
    std::cin >> n >> L;
    std::vector<std::vector<int>> p(n, std::vector<int>(2, 0));
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i][0] >> p[i][1];
        p[i][1] = abs(p[i][1]);
    }
    sort(p.begin(), p.end());
    double lo = 0.0, hi = 4e9;
    while(hi - lo > 1e-6) {
        double mi = lo + (hi - lo) / 2;
        double cur = 0.0;
        for (int i = 0; i < n; ++i) {
            double h = p[i][1];
            if (h > mi)
                continue;
            double d = sqrt(mi * mi - h * h);
            if (cur >= p[i][0] - d)
                cur = std::max(cur, p[i][0] + d);
        }
        if (cur >= L) {
            hi = mi;
        }
        else {
            lo = mi;
        }
    }
    std::cout << std::setprecision(10) << lo << "\n";
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	460 KB	Output is correct
2	Correct	3 ms	588 KB	Output is correct
3	Correct	3 ms	560 KB	Output is correct
4	Correct	3 ms	460 KB	Output is correct
5	Correct	3 ms	560 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	4300 KB	Output is correct
2	Correct	49 ms	4516 KB	Output is correct
3	Correct	29 ms	3148 KB	Output is correct
4	Correct	39 ms	4344 KB	Output is correct
5	Correct	26 ms	3020 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	4556 KB	Output is correct
2	Correct	36 ms	4172 KB	Output is correct
3	Correct	40 ms	4712 KB	Output is correct
4	Correct	42 ms	4564 KB	Output is correct
5	Correct	42 ms	4940 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	5068 KB	Output is correct
2	Correct	58 ms	4812 KB	Output is correct
3	Correct	46 ms	4940 KB	Output is correct
4	Correct	49 ms	5708 KB	Output is correct
5	Correct	45 ms	5196 KB	Output is correct

Subtask #10
0 / 5.0

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

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	5708 KB	Output is correct
2	Correct	61 ms	5708 KB	Output is correct
3	Correct	57 ms	5708 KB	Output is correct
4	Correct	50 ms	5708 KB	Output is correct
5	Correct	50 ms	5708 KB	Output is correct

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	27664 KB	Output is correct
2	Incorrect	315 ms	27604 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	326 ms	27592 KB	Output is correct
2	Correct	356 ms	27656 KB	Output is correct
3	Correct	297 ms	27588 KB	Output is correct
4	Correct	288 ms	27620 KB	Output is correct
5	Correct	275 ms	27596 KB	Output is correct

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	33176 KB	Output is correct
2	Incorrect	388 ms	33092 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	413 ms	38596 KB	Output is correct
2	Incorrect	457 ms	38656 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	469 ms	38648 KB	Output is correct
2	Correct	485 ms	38604 KB	Output is correct
3	Correct	423 ms	38656 KB	Output is correct
4	Correct	402 ms	38568 KB	Output is correct
5	Correct	416 ms	38596 KB	Output is correct

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	473 ms	44100 KB	Output is correct
2	Incorrect	511 ms	44052 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	519 ms	44124 KB	Output is correct
2	Correct	535 ms	44120 KB	Output is correct
3	Correct	475 ms	44068 KB	Output is correct
4	Correct	469 ms	44100 KB	Output is correct
5	Correct	463 ms	44092 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	604 ms	54980 KB	Output is correct
2	Incorrect	648 ms	54980 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	641 ms	54980 KB	Output is correct
2	Correct	659 ms	55012 KB	Output is correct
3	Correct	598 ms	55060 KB	Output is correct
4	Correct	579 ms	54980 KB	Output is correct
5	Correct	569 ms	54980 KB	Output is correct

Submission #464195

Compilation message