Submission #819919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
819919	2023-08-10T15:38:10 Z	Peter_Peter	Mobile (BOI12_mobile)	C++17	100 / 100	414 ms	35284 KB

mobile

// ~uped
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    fastio();
    int n, len;
    cin >> n >> len;
    vector<pair<ll, ll>> v(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        v[i] = {a, b};
    }
    // binary search radius
    double l = 0.0, r = 1e10;
    while (r - l > 1e-3) {
        double radius = (l + r) / 2.0;
        double mx = 0;
        for (int j = 0; j < n; ++j) {
            ll x = v[j].first;
            ll y = v[j].second;
            // a*a+b*b=c*c => c*c-b*b=a*a
            double a = sqrt( radius * radius - y * y);
            // we cover segment from x - a to x + a
            if (x - a <= mx) {
                mx = max(x + a, mx);
            }
        }
        if (mx >= len) {
            r = radius;
        } else {
            l = radius;
        }
    }
    cout << setprecision(20) << r;
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2260 KB	Output is correct
2	Correct	21 ms	2544 KB	Output is correct
3	Correct	14 ms	1748 KB	Output is correct
4	Correct	28 ms	2652 KB	Output is correct
5	Correct	15 ms	1492 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2176 KB	Output is correct
2	Correct	25 ms	2132 KB	Output is correct
3	Correct	27 ms	2516 KB	Output is correct
4	Correct	28 ms	2644 KB	Output is correct
5	Correct	30 ms	3028 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2260 KB	Output is correct
2	Correct	22 ms	2764 KB	Output is correct
3	Correct	21 ms	2516 KB	Output is correct
4	Correct	39 ms	3788 KB	Output is correct
5	Correct	26 ms	2644 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	3408 KB	Output is correct
2	Correct	27 ms	3284 KB	Output is correct
3	Correct	25 ms	2900 KB	Output is correct
4	Correct	40 ms	3788 KB	Output is correct
5	Correct	34 ms	3036 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	3292 KB	Output is correct
2	Correct	27 ms	3284 KB	Output is correct
3	Correct	25 ms	2904 KB	Output is correct
4	Correct	36 ms	3796 KB	Output is correct
5	Correct	31 ms	3152 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	120 ms	12348 KB	Output is correct
2	Correct	131 ms	15804 KB	Output is correct
3	Correct	147 ms	15292 KB	Output is correct
4	Correct	176 ms	17596 KB	Output is correct
5	Correct	179 ms	14852 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	16316 KB	Output is correct
2	Correct	208 ms	14668 KB	Output is correct
3	Correct	124 ms	13772 KB	Output is correct
4	Correct	195 ms	17356 KB	Output is correct
5	Correct	178 ms	15420 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	14796 KB	Output is correct
2	Correct	163 ms	18920 KB	Output is correct
3	Correct	153 ms	18280 KB	Output is correct
4	Correct	217 ms	21472 KB	Output is correct
5	Correct	187 ms	17628 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	181 ms	19528 KB	Output is correct
2	Correct	247 ms	17500 KB	Output is correct
3	Correct	162 ms	16484 KB	Output is correct
4	Correct	221 ms	21336 KB	Output is correct
5	Correct	191 ms	18380 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	17284 KB	Output is correct
2	Correct	190 ms	22012 KB	Output is correct
3	Correct	178 ms	21380 KB	Output is correct
4	Correct	249 ms	24696 KB	Output is correct
5	Correct	226 ms	20236 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	22776 KB	Output is correct
2	Correct	264 ms	20476 KB	Output is correct
3	Correct	186 ms	19580 KB	Output is correct
4	Correct	262 ms	24572 KB	Output is correct
5	Correct	223 ms	21380 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	188 ms	19732 KB	Output is correct
2	Correct	222 ms	25116 KB	Output is correct
3	Correct	212 ms	24352 KB	Output is correct
4	Correct	290 ms	28440 KB	Output is correct
5	Correct	251 ms	23972 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	26008 KB	Output is correct
2	Correct	296 ms	23320 KB	Output is correct
3	Correct	200 ms	22292 KB	Output is correct
4	Correct	292 ms	28192 KB	Output is correct
5	Correct	253 ms	24400 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	230 ms	24536 KB	Output is correct
2	Correct	310 ms	31448 KB	Output is correct
3	Correct	256 ms	30432 KB	Output is correct
4	Correct	364 ms	35024 KB	Output is correct
5	Correct	329 ms	29524 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	32336 KB	Output is correct
2	Correct	370 ms	29144 KB	Output is correct
3	Correct	260 ms	28244 KB	Output is correct
4	Correct	414 ms	35284 KB	Output is correct
5	Correct	358 ms	30688 KB	Output is correct

Submission #819919

Compilation message