oj.uz

Submission #595049

# Submission time Handle Problem Language Result Execution time Memory
595049 2022-07-13T09:51:53 Z hail Mobile (BOI12_mobile) C++17
90 / 100
 1000 ms 16068 KB 
#include <bits/stdc++.h>

using namespace std;

using pld = pair<double, double>;
using ld = double;

#define mp make_pair

int n;
ld l;
pld station[(int)1e6];

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

bool check_dist(ld r)
{
    if(r<0) return false;
    pld ret_int;
    ld from_x=0;
    /*
    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;
    */
   pld circ;
    for(int i=0; i<n; i++)
    {
        circ=station[i];
        if(circ.first>from_x+r) 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;

    ld 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});
    }

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

    cout<<high;

}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1428 KB Output is correct
2 Correct 41 ms 1484 KB Output is correct
3 Correct 31 ms 1100 KB Output is correct
4 Correct 43 ms 1476 KB Output is correct
5 Correct 25 ms 1056 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1484 KB Output is correct
2 Correct 34 ms 1364 KB Output is correct
3 Correct 40 ms 1572 KB Output is correct
4 Correct 44 ms 1444 KB Output is correct
5 Correct 53 ms 1612 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1688 KB Output is correct
2 Correct 43 ms 1560 KB Output is correct
3 Correct 59 ms 1604 KB Output is correct
4 Correct 62 ms 1820 KB Output is correct
5 Correct 44 ms 1576 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1852 KB Output is correct
2 Correct 51 ms 1772 KB Output is correct
3 Correct 62 ms 1788 KB Output is correct
4 Correct 61 ms 1868 KB Output is correct
5 Correct 49 ms 1852 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1868 KB Output is correct
2 Correct 46 ms 1816 KB Output is correct
3 Correct 58 ms 1868 KB Output is correct
4 Correct 63 ms 1812 KB Output is correct
5 Correct 50 ms 1812 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8140 KB Output is correct
2 Correct 241 ms 8040 KB Output is correct
3 Correct 233 ms 8048 KB Output is correct
4 Correct 328 ms 8056 KB Output is correct
5 Correct 256 ms 8100 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8172 KB Output is correct
2 Correct 388 ms 8064 KB Output is correct
3 Correct 301 ms 8136 KB Output is correct
4 Correct 315 ms 8136 KB Output is correct
5 Correct 267 ms 8036 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 9704 KB Output is correct
2 Correct 293 ms 9676 KB Output is correct
3 Correct 284 ms 9608 KB Output is correct
4 Correct 390 ms 9744 KB Output is correct
5 Correct 318 ms 9700 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 9616 KB Output is correct
2 Correct 456 ms 9868 KB Output is correct
3 Correct 355 ms 9776 KB Output is correct
4 Correct 395 ms 9708 KB Output is correct
5 Correct 324 ms 9680 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 11336 KB Output is correct
2 Correct 341 ms 11260 KB Output is correct
3 Correct 327 ms 11424 KB Output is correct
4 Correct 449 ms 11176 KB Output is correct
5 Correct 349 ms 11268 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 11192 KB Output is correct
2 Correct 530 ms 11164 KB Output is correct
3 Correct 431 ms 11268 KB Output is correct
4 Correct 495 ms 11316 KB Output is correct
5 Correct 375 ms 11332 KB Output is correct

Subtask #18
0 / 5.0

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

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 12788 KB Output is correct
2 Correct 631 ms 12836 KB Output is correct
3 Correct 485 ms 12840 KB Output is correct
4 Correct 501 ms 12716 KB Output is correct
5 Correct 482 ms 12768 KB Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 15916 KB Output is correct
2 Correct 775 ms 15936 KB Output is correct
3 Correct 655 ms 16068 KB Output is correct
4 Correct 630 ms 15952 KB Output is correct
5 Correct 555 ms 15952 KB Output is correct