oj.uz

Submission #916398

# Submission time Handle Problem Language Result Execution time Memory
916398 2024-01-25T19:40:52 Z asdasdqwer Mobile (BOI12_mobile) C++14
85 / 100
 1000 ms 84724 KB 
#pragma GCC optimize("O3")

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

#define int int64_t
#define pii array<int,2>


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n,t;cin>>n>>t;
    vector<pii> v(n);
    for (auto &x:v)cin>>x[0]>>x[1];

    vector<pii> tt;
    for (auto &x:v) {
        if (!tt.size()) {
            tt.push_back(x);
        }

        else if (tt.back()[0] == x[0] && abs(tt.back()[1]) > abs(x[1])) {
            tt.pop_back();
        }
        tt.push_back(x);
    }

    // v=tt;
    n=v.size();

    long double l = 1;
    long double r = 1e10;

    cout<<setprecision(15);

    // for (auto &x:v) {
    //     r = min(r, (long double)max(sqrt(x[0]*x[0] + x[1]*x[1]), sqrt((x[0]-t)*(x[0]-t) + x[1]*x[1])));
    // }

    // cout<<r<<"\n";

    // vector<bool> rem(n, false);
    
    while (abs(l-r) > 0.0001) {
        long double m = (l+r)/2.0;
        int i=0;
        vector<array<long double,2>> start;
        bool all=false;
        
        for (auto &x:v) {
            if ((double)abs(x[1]) >= m) {
                // rem[i]=true;
                continue;
            }

            // if (rem[i]) {
            //     i++;
            //     continue;
            // }
    
            else {
                long double aa=(double)abs(x[1]);
                long double dis=sqrt(m*m-aa*aa);
                array<long 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)) {
                    // rem[i]=true;
                    continue;
                }
    
                else {
                    pos1[0]=max(pos1[0], (long double)0.0);
                    pos1[1]=min(pos1[1], (long double)t);
                    if (pos1[0] == 0.0 && pos1[1] == t) {
                        all=true;
                        break;
                    }

                    start.push_back(pos1);
                }
            }
    
            i++;
        }

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

        bool possible=true;

        double e=0.0;

        for (auto &x:start) {
            if (x[0] <= e && x[1] > e) {
                e=x[1];
            }
        }

        if (e<t) possible=false;
    
        if (possible) {
            r=m;
            // int cnt=0;
            // int pt=0;
            // for (int i=0;i<n;i++) {
            //     if (rem[i]) {
            //         cnt++;
            //     }
                
            //     else if (cnt != 0) {
            //         swap(v[i], v[pt]);
            //     }
    
            //     if (!rem[i]) {
            //         pt++;
            //     }
            // }
    
            // n -= cnt;
    
            // while (v.size() != n){
            //     v.pop_back();
            //     rem.pop_back();
            // }
    
            // for (int i=0;i<n;i++) {
            //     rem[i]=false;
            // }
        }
    
        else {
            l=m;
            // for (i=0;i<n;i++) {
            //     rem[i]=false;
            // }
        }
    }
    cout<<r<<"\n";
}

Subtask #1
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6152 KB Output is correct
2 Correct 68 ms 10916 KB Output is correct
3 Correct 53 ms 6276 KB Output is correct
4 Correct 23 ms 4308 KB Output is correct
5 Correct 10 ms 2300 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3836 KB Output is correct
2 Correct 19 ms 3800 KB Output is correct
3 Correct 22 ms 4416 KB Output is correct
4 Correct 26 ms 4564 KB Output is correct
5 Correct 29 ms 4676 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10416 KB Output is correct
2 Correct 61 ms 9876 KB Output is correct
3 Correct 44 ms 7164 KB Output is correct
4 Correct 39 ms 5476 KB Output is correct
5 Correct 22 ms 4288 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10904 KB Output is correct
2 Correct 79 ms 10880 KB Output is correct
3 Correct 52 ms 10048 KB Output is correct
4 Correct 33 ms 5284 KB Output is correct
5 Correct 26 ms 5364 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 11132 KB Output is correct
2 Correct 75 ms 10888 KB Output is correct
3 Correct 60 ms 10824 KB Output is correct
4 Correct 33 ms 5332 KB Output is correct
5 Correct 28 ms 5164 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 48256 KB Output is correct
2 Correct 403 ms 48796 KB Output is correct
3 Correct 420 ms 48956 KB Output is correct
4 Correct 151 ms 28884 KB Output is correct
5 Correct 131 ms 23768 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 48888 KB Output is correct
2 Correct 380 ms 42888 KB Output is correct
3 Correct 392 ms 44912 KB Output is correct
4 Correct 152 ms 24024 KB Output is correct
5 Correct 134 ms 28872 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 71856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 69972 KB Output is correct
2 Correct 455 ms 49248 KB Output is correct
3 Correct 304 ms 53644 KB Output is correct
4 Correct 206 ms 34772 KB Output is correct
5 Correct 160 ms 33756 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 73216 KB Output is correct
2 Correct 851 ms 84724 KB Output is correct
3 Correct 641 ms 84180 KB Output is correct
4 Correct 265 ms 51620 KB Output is correct
5 Correct 181 ms 41564 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 73388 KB Output is correct
2 Correct 534 ms 73268 KB Output is correct
3 Correct 442 ms 55940 KB Output is correct
4 Correct 217 ms 38336 KB Output is correct
5 Correct 190 ms 36360 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 76832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 78108 KB Output is correct
2 Correct 583 ms 75028 KB Output is correct
3 Correct 558 ms 78400 KB Output is correct
4 Correct 253 ms 42180 KB Output is correct
5 Correct 232 ms 40820 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 83148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 81652 KB Output is correct
2 Correct 716 ms 81872 KB Output is correct
3 Correct 789 ms 81884 KB Output is correct
4 Correct 312 ms 58756 KB Output is correct
5 Correct 264 ms 56916 KB Output is correct