Submission #916413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916413	2024-01-25T20:02:41 Z	asdasdqwer	Mobile (BOI12_mobile)	C++14	100 / 100	315 ms	23992 KB

mobile

#pragma GCC optimize("O3")

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

#define pii array<int,2>
#define MAXN 1000001

array<double,2> start[MAXN];
int point=0;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,t;cin>>n>>t;
    vector<pii> v;
    for (int i=0;i<n;i++) {
        int a,b;cin>>a>>b;
        if (v.size() && v.back()[0] == a) {
            if (abs(v.back()[1]) > b) {
                v.pop_back();
                v.push_back({a,b});
            }
        }

        else {
            v.push_back({a,b});
        }
    }

    n=v.size();

    double l = 1;
    double r = 1e10;

    cout<<setprecision(15);

    while (abs(l-r) > 0.001) {
        point = 0;
        double m = (l+r)/2.0;
        int i=0;
        bool all=false;
        
        for (auto &x:v) {
            if ((double)abs(x[1]) >= m) {
                i++;
                continue;
            }
    
            else {
                double aa=(double)abs(x[1]);
                double dis=sqrt(m*m-aa*aa);
                array<double,2> pos1 = {x[0]-dis,x[0]+dis};
                if ((pos1[0] < 0.0 && pos1[1] < 0.0) || (pos1[0] > (double)t && pos1[1] > (double)t)) {
                    i++;
                    continue;
                }
    
                else {
                    pos1[0]=max(pos1[0], 0.0);
                    pos1[1]=min(pos1[1], (double)t);
                    if (pos1[0] == 0.0 && pos1[1] == t) {
                        all=true;
                        break;
                    }

                    start[point++] = pos1;
                }
            }
    
            i++;
        }

        if (all) {
            r=m;
            continue;
        }

        bool possible=true;

        double e=0.0;

        for (int i=0;i<point;i++) {
            if (start[i][0] <= e && start[i][1] > e) {
                e=start[i][1];
            }
        }

        if (e<t) possible=false;
    
        if (possible) {
            r=m;
        }
    
        else {
            l=m;
        }
    }

    cout<<r<<"\n";
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	344 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	Memory	Grader output
1	Correct	344 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 #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 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	2 ms	604 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3288 KB	Output is correct
2	Correct	15 ms	3032 KB	Output is correct
3	Correct	12 ms	3036 KB	Output is correct
4	Correct	16 ms	3288 KB	Output is correct
5	Correct	5 ms	348 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	604 KB	Output is correct
2	Correct	11 ms	992 KB	Output is correct
3	Correct	15 ms	3300 KB	Output is correct
4	Correct	16 ms	3284 KB	Output is correct
5	Correct	18 ms	3288 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	3288 KB	Output is correct
2	Correct	16 ms	3036 KB	Output is correct
3	Correct	16 ms	3288 KB	Output is correct
4	Correct	23 ms	3540 KB	Output is correct
5	Correct	12 ms	856 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3220 KB	Output is correct
2	Correct	16 ms	3032 KB	Output is correct
3	Correct	12 ms	856 KB	Output is correct
4	Correct	22 ms	3540 KB	Output is correct
5	Correct	17 ms	3284 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	3540 KB	Output is correct
2	Correct	16 ms	2988 KB	Output is correct
3	Correct	12 ms	1116 KB	Output is correct
4	Correct	23 ms	3544 KB	Output is correct
5	Correct	18 ms	3284 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	12728 KB	Output is correct
2	Correct	63 ms	592 KB	Output is correct
3	Correct	62 ms	544 KB	Output is correct
4	Correct	107 ms	8712 KB	Output is correct
5	Correct	85 ms	5128 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	560 KB	Output is correct
2	Correct	185 ms	10688 KB	Output is correct
3	Correct	63 ms	3532 KB	Output is correct
4	Correct	103 ms	6604 KB	Output is correct
5	Correct	89 ms	6592 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	195 ms	17596 KB	Output is correct
2	Correct	75 ms	804 KB	Output is correct
3	Correct	73 ms	500 KB	Output is correct
4	Correct	132 ms	10168 KB	Output is correct
5	Correct	97 ms	7608 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	592 KB	Output is correct
2	Correct	199 ms	14004 KB	Output is correct
3	Correct	68 ms	3104 KB	Output is correct
4	Correct	128 ms	9556 KB	Output is correct
5	Correct	106 ms	10772 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	19200 KB	Output is correct
2	Correct	87 ms	596 KB	Output is correct
3	Correct	87 ms	596 KB	Output is correct
4	Correct	152 ms	12144 KB	Output is correct
5	Correct	103 ms	6564 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	596 KB	Output is correct
2	Correct	215 ms	17832 KB	Output is correct
3	Correct	88 ms	3788 KB	Output is correct
4	Correct	147 ms	10676 KB	Output is correct
5	Correct	123 ms	9636 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	22996 KB	Output is correct
2	Correct	101 ms	496 KB	Output is correct
3	Correct	97 ms	480 KB	Output is correct
4	Correct	175 ms	11260 KB	Output is correct
5	Correct	138 ms	8760 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	544 KB	Output is correct
2	Correct	266 ms	18452 KB	Output is correct
3	Correct	116 ms	3528 KB	Output is correct
4	Correct	173 ms	11192 KB	Output is correct
5	Correct	140 ms	10940 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	315 ms	23992 KB	Output is correct
2	Correct	125 ms	468 KB	Output is correct
3	Correct	120 ms	468 KB	Output is correct
4	Correct	215 ms	14692 KB	Output is correct
5	Correct	160 ms	8388 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	508 KB	Output is correct
2	Correct	289 ms	20728 KB	Output is correct
3	Correct	126 ms	4012 KB	Output is correct
4	Correct	212 ms	14516 KB	Output is correct
5	Correct	178 ms	11704 KB	Output is correct

Submission #916413

Compilation message