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