oj.uz

Submission #596242

# Submission time Handle Problem Language Result Execution time Memory
596242 2022-07-14T14:03:19 Z hail Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 32452 KB 
#include <bits/stdc++.h>

using namespace std;

using pd = pair<double, double>;

int max_ind{};
int max_x{};

#define mp make_pair

int n;
double l;
int max_reach{};
pd station[(int)1e6];

pd intercept(pd coor, double r)
{
    if(abs(coor.second)>r) return mp(-1, -1);
    double mid = pow(r, 2)-pow(coor.second, 2);
    double rt_mid = pow(mid , 0.5);
    return mp(coor.first-rt_mid, coor.first+rt_mid);
}

bool check_dist(double r)
{
    if(r<0) return false;
    pd ret_int;
    double from_x;
    if(max_reach==0)
    {
        from_x= max((intercept(station[0], r)).second, 0.0);
    }
    else
    {
        from_x=intercept(station[max_reach-1], r).second;
    }
    /*
    auto it=lower_bound(station.begin(), station.end(), mp(-r, -1e9));
    while(it<station.end())
    {
        if((*it).first>from_x+r) return false;
        ret_int=intercept(*it, r);
        if(ret_int.first<=from_x && ret_int.second>from_x)
        {
            from_x=ret_int.second;
            if(from_x>=l) return true;
            it = upper_bound(it+1, station.end(), mp(from_x-r, 1e9));
        }
        else it++;
    }
    return false;
    */
   pd circ;
    for(int i=max_reach; i<n; i++)
    {
        circ=station[i];
        if(circ.first>from_x+r)
        {
            max_reach=i;
            return false;
        }
        if(circ.first>from_x-r)
        {
            ret_int=intercept(circ, r);
            if(ret_int.first<=from_x && ret_int.second>from_x)
            {
                from_x=ret_int.second;
                if(from_x>=l) return true;
            }
        }
        
    }

    return false;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cout<<setprecision(20); 

    cin>>n>>l;

    double max_coor{};

    for(int i=0; i<n; i++)
    {
        cin>>station[i].first>>station[i].second;
        max_coor=max({abs(station[i].first), abs(station[i].second), max_coor});
    }

    double high=2*(max_coor+l);
    double low=0;
    double mid;
    while(high-low>=1e-3)
    {
        mid=(high+low)/2;
        if(check_dist(mid)) high=mid;
        else low=mid;
    }

    cout<<high;

}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 2356 KB Output is correct
2 Incorrect 40 ms 2720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 12424 KB Output is correct
2 Incorrect 271 ms 15732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 14968 KB Output is correct
2 Incorrect 307 ms 18944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 17336 KB Output is correct
2 Incorrect 342 ms 22100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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