Submission #553428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
553428	2022-04-25T19:39:47 Z	Hona_Nguyen	Mobile (BOI12_mobile)	C++14	100 / 100	887 ms	35404 KB

mobile

#include<bits/stdc++.h>
#define prob "mobile"
#define x first
#define y second
using namespace std;
const int maxn = 1e6;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
int n,L;
pair<double,double> p[maxn+5];
int main(){
//    freopen(prob".in","r",stdin);
//    freopen(prob".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> L;
    for(int i=1;i<=n;i++) cin >> p[i].x >> p[i].y;
    auto check = [&](double val) -> int{
//        vector<pair<double,double>> G;
        double curx = 0;
        for(int i=1;i<=n;i++){
//            if(val < p[i].y) return 0;
            double tmp = sqrt(val*val-p[i].y*p[i].y);
            double xL = p[i].x - tmp;
            double xR = p[i].x + tmp;
            if(xL <= curx){
                curx = max(curx, xR);
            }
//            G.push_back(make_pair(xL,xR));
        }
//        sort(G.begin(),G.end(), [](const pair<double,double> A, const pair<double,double> B){
//             if(A.first == B.first) return A.second < B.second;
//             return A.first < B.first;
//             });

//        for(int i=0;i<n;i++){
//            if(G[i].x <= curx){
//               curx = max(curx, G[i].y);
//            }
//        }
        if(curx >= (double)(L)) return 1;
        return 0;
    };
    double low = 1, high = (double)(1.5e9), res = 0;
    for(int i=1;i<=100;i++){
        if(high - low < eps) break;
        double mid = (low + high) / (double)(2);
        if(check(mid)){
            res = mid;
            high = mid;
        }
        else{
            low = mid;
        }
    }
    cout << fixed << setprecision(6);
    cout << res;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.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	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	1416 KB	Output is correct
2	Correct	57 ms	1468 KB	Output is correct
3	Correct	32 ms	1108 KB	Output is correct
4	Correct	58 ms	1436 KB	Output is correct
5	Correct	30 ms	1116 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	1420 KB	Output is correct
2	Correct	50 ms	1364 KB	Output is correct
3	Correct	58 ms	1584 KB	Output is correct
4	Correct	60 ms	1552 KB	Output is correct
5	Correct	68 ms	1636 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	1612 KB	Output is correct
2	Correct	67 ms	1544 KB	Output is correct
3	Correct	52 ms	1632 KB	Output is correct
4	Correct	87 ms	1964 KB	Output is correct
5	Correct	58 ms	1700 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	1872 KB	Output is correct
2	Correct	75 ms	1860 KB	Output is correct
3	Correct	57 ms	1872 KB	Output is correct
4	Correct	84 ms	1936 KB	Output is correct
5	Correct	71 ms	1796 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	1832 KB	Output is correct
2	Correct	74 ms	1788 KB	Output is correct
3	Correct	59 ms	1788 KB	Output is correct
4	Correct	82 ms	1872 KB	Output is correct
5	Correct	78 ms	1812 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	8132 KB	Output is correct
2	Correct	374 ms	8492 KB	Output is correct
3	Correct	318 ms	8460 KB	Output is correct
4	Correct	424 ms	8660 KB	Output is correct
5	Correct	362 ms	14956 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	405 ms	8104 KB	Output is correct
2	Correct	433 ms	8436 KB	Output is correct
3	Correct	303 ms	13880 KB	Output is correct
4	Correct	440 ms	17412 KB	Output is correct
5	Correct	404 ms	15556 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	9708 KB	Output is correct
2	Correct	512 ms	18972 KB	Output is correct
3	Correct	398 ms	18364 KB	Output is correct
4	Correct	518 ms	21576 KB	Output is correct
5	Correct	457 ms	17720 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	9700 KB	Output is correct
2	Correct	536 ms	17620 KB	Output is correct
3	Correct	363 ms	16532 KB	Output is correct
4	Correct	508 ms	21416 KB	Output is correct
5	Correct	463 ms	18368 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	459 ms	11264 KB	Output is correct
2	Correct	545 ms	22116 KB	Output is correct
3	Correct	442 ms	21376 KB	Output is correct
4	Correct	592 ms	24796 KB	Output is correct
5	Correct	514 ms	20404 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	538 ms	11300 KB	Output is correct
2	Correct	601 ms	20408 KB	Output is correct
3	Correct	484 ms	19680 KB	Output is correct
4	Correct	577 ms	24564 KB	Output is correct
5	Correct	516 ms	21328 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	542 ms	12748 KB	Output is correct
2	Correct	600 ms	25280 KB	Output is correct
3	Correct	511 ms	24452 KB	Output is correct
4	Correct	693 ms	28360 KB	Output is correct
5	Correct	590 ms	23944 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	691 ms	12816 KB	Output is correct
2	Correct	700 ms	23348 KB	Output is correct
3	Correct	504 ms	22400 KB	Output is correct
4	Correct	685 ms	28188 KB	Output is correct
5	Correct	600 ms	24408 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	663 ms	15956 KB	Output is correct
2	Correct	775 ms	31476 KB	Output is correct
3	Correct	659 ms	30552 KB	Output is correct
4	Correct	887 ms	35120 KB	Output is correct
5	Correct	730 ms	29644 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	787 ms	15968 KB	Output is correct
2	Correct	852 ms	29148 KB	Output is correct
3	Correct	641 ms	28232 KB	Output is correct
4	Correct	857 ms	35404 KB	Output is correct
5	Correct	749 ms	30660 KB	Output is correct

Submission #553428

Compilation message