Submission #1063749

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063749	2024-08-18T01:01:43 Z	daviedu	Mobile (BOI12_mobile)	C++17	100 / 100	961 ms	46488 KB

mobile

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define ld long double

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const ld prec = 0.0005;
const ld MX = 2e9;
vector<pair<ld, ld>> points;
int n, len;

bool f(ld r){
    ld right=0;
    for (auto& [x, y]: points){
        if (r < y) continue;
        ld dx = sqrtl(r*r - y*y);
        if (x-dx <= right) right = max(right, x+dx);
    }
    return right >= len;
}

signed main(){
    fastio;
    cin >> n >> len;
    points.resize(n);
    for (int i=0; i<n; i++){
        cin >> points[i].first;
        cin >> points[i].second;
    }
    
    ld l=0, r=MX, ans=MX;
    while (r-l >= prec){
        ld m = (l+r)/2;
        if (f(m)) r = m, ans = m;
        else l = m;
    }
    cout << fixed << setprecision(13);
    cout << ans << '\n';
}

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	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	420 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	2652 KB	Output is correct
2	Correct	37 ms	2652 KB	Output is correct
3	Correct	25 ms	2140 KB	Output is correct
4	Correct	63 ms	2652 KB	Output is correct
5	Correct	29 ms	1884 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	2904 KB	Output is correct
2	Correct	53 ms	2648 KB	Output is correct
3	Correct	62 ms	2908 KB	Output is correct
4	Correct	65 ms	2908 KB	Output is correct
5	Correct	82 ms	3160 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	3164 KB	Output is correct
2	Correct	40 ms	2908 KB	Output is correct
3	Correct	38 ms	2908 KB	Output is correct
4	Correct	100 ms	3416 KB	Output is correct
5	Correct	75 ms	3168 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	3420 KB	Output is correct
2	Correct	48 ms	3420 KB	Output is correct
3	Correct	44 ms	3420 KB	Output is correct
4	Correct	101 ms	3416 KB	Output is correct
5	Correct	77 ms	3420 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	3420 KB	Output is correct
2	Correct	48 ms	3420 KB	Output is correct
3	Correct	49 ms	3416 KB	Output is correct
4	Correct	93 ms	3416 KB	Output is correct
5	Correct	78 ms	3420 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	15964 KB	Output is correct
2	Correct	249 ms	15964 KB	Output is correct
3	Correct	287 ms	15972 KB	Output is correct
4	Correct	465 ms	15960 KB	Output is correct
5	Correct	411 ms	15964 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	15964 KB	Output is correct
2	Correct	272 ms	15964 KB	Output is correct
3	Correct	238 ms	15964 KB	Output is correct
4	Correct	456 ms	15960 KB	Output is correct
5	Correct	438 ms	15960 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	19032 KB	Output is correct
2	Correct	322 ms	19036 KB	Output is correct
3	Correct	299 ms	19036 KB	Output is correct
4	Correct	568 ms	19036 KB	Output is correct
5	Correct	474 ms	19036 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	315 ms	19032 KB	Output is correct
2	Correct	342 ms	19036 KB	Output is correct
3	Correct	304 ms	19036 KB	Output is correct
4	Correct	558 ms	19032 KB	Output is correct
5	Correct	502 ms	19032 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	365 ms	22364 KB	Output is correct
2	Correct	344 ms	22364 KB	Output is correct
3	Correct	344 ms	22616 KB	Output is correct
4	Correct	664 ms	22360 KB	Output is correct
5	Correct	561 ms	22360 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	330 ms	22360 KB	Output is correct
2	Correct	371 ms	22360 KB	Output is correct
3	Correct	318 ms	22288 KB	Output is correct
4	Correct	662 ms	22364 KB	Output is correct
5	Correct	574 ms	22364 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	413 ms	25436 KB	Output is correct
2	Correct	417 ms	25432 KB	Output is correct
3	Correct	419 ms	25432 KB	Output is correct
4	Correct	770 ms	25432 KB	Output is correct
5	Correct	648 ms	25436 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	25436 KB	Output is correct
2	Correct	427 ms	25452 KB	Output is correct
3	Correct	364 ms	25436 KB	Output is correct
4	Correct	779 ms	25436 KB	Output is correct
5	Correct	678 ms	25436 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	514 ms	31580 KB	Output is correct
2	Correct	496 ms	31580 KB	Output is correct
3	Correct	488 ms	31580 KB	Output is correct
4	Correct	961 ms	31576 KB	Output is correct
5	Correct	802 ms	45140 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	488 ms	31576 KB	Output is correct
2	Correct	518 ms	31576 KB	Output is correct
3	Correct	459 ms	31580 KB	Output is correct
4	Correct	935 ms	31644 KB	Output is correct
5	Correct	873 ms	46488 KB	Output is correct

Submission #1063749

Compilation message