oj.uz

Submission #1094989

# Submission time Handle Problem Language Result Execution time Memory
1094989 2024-10-01T06:17:53 Z Kodik Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 105980 KB 
#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
typedef long double ld;
#define int ll




bool check(const ld& l,const ld& radius,const vector<pair<ld,ld>> &bases){
    stack<pair<bool,ld>> st; // bool 1 = start, 0 end
    for(auto &[x, y] : bases){
        ld x_on_highway = sqrtl(radius*radius-y*y);
        ld start = x - x_on_highway;
        ld end = x + x_on_highway;
        bool push_start = true;
        while(!st.empty()){
            ld cor = st.top().ss; 
            /*
            if my start is earlier than last ending or starting we can remove them, at the end
            all we want not to end when there is no start
            */
            if(start<=cor){
                if(!st.top().ff){
                    push_start = 0;
                }else if(st.top().ff){
                    push_start = 1;
                }
                st.pop();
            }else{
                break;
            }
        }
        if(push_start) st.push({1,start}); // do we push start if we removed only end !no
        st.push({0,end});
    }
    bool ok = (st.size()==2);
    /*
    if everything is correct, the 
    we should have in stack only start and end
    if we dont then that means than somwhere we have a not covered interval
    */
    while(!st.empty()){
        if(ok){
            if(!st.top().ff){
                ok &= (st.top().ss>=l);
            }else if(st.top().ff){
                ok &= (st.top().ss<=0);
            }
            st.pop();
        }else{
            break;
        }
    }
    return ok;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ld n, l; 
    cin >> n >> l;
    vector<pair<ld,ld>> bases(n);
    for(int i = 0; i < n; ++i){
        ld x, y;
        cin >> x >> y;
        bases[i] = {x,abs(y)}; // shouldnt be a problem to set y to its abs
    }
    sort(bases.begin(), bases.end(), [&](const auto&a,const auto&b){
        if(a.ff==b.ff){
            return a.ss < b.ss; // we want to have the closest first, becasue it will cover the geaters interval
        }
        return a.ff < b.ff;
    });
    ld left = 0, right = 2e9;
    while(right-left>1e-7){
        ld mid = left + (right-left)/2;
        if(check(left,mid, bases)){
            // ak sedi zmensujem
            right = mid;
        }else{
            left = mid;
        }
    }
    cout << fixed << setprecision(3) << right;
    return 0;   
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 924 KB Output is correct
2 Correct 8 ms 464 KB Output is correct
3 Incorrect 7 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 8488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 6228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 9688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4956 KB Output is correct
2 Correct 167 ms 4864 KB Output is correct
3 Incorrect 176 ms 7436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 4868 KB Output is correct
2 Correct 145 ms 5000 KB Output is correct
3 Incorrect 145 ms 7508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 929 ms 53228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 24072 KB Output is correct
2 Incorrect 788 ms 55404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 29008 KB Output is correct
2 Incorrect 962 ms 66332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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