oj.uz

Submission #593233

# Submission time Handle Problem Language Result Execution time Memory
593233 2022-07-10T15:47:49 Z hail Mobile (BOI12_mobile) C++17
30 / 100
 1000 ms 29264 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define mp make_pair

int n;
ld l;
vector<pld> station;

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

bool check_dist(ld r)
{
    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(station.begin(), station.end(), mp(from_x-r, 1e9));
        }
        else it++;
    }
    return false;
}


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

    cout<<setprecision(11);

    cin>>n>>l;
    station.resize(n);

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

    ld high=2e9;
    ld low=0;
    ld mid;
    while(high-low>=1e-4)
    {
        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 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 388 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 592 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 5 ms 468 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1620 KB Output is correct
2 Correct 35 ms 2532 KB Output is correct
3 Execution timed out 1087 ms 1668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1608 KB Output is correct
2 Correct 35 ms 2180 KB Output is correct
3 Correct 42 ms 2608 KB Output is correct
4 Correct 49 ms 2708 KB Output is correct
5 Correct 53 ms 3020 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 1748 KB Output is correct
2 Correct 38 ms 2636 KB Output is correct
3 Execution timed out 1087 ms 2532 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 2004 KB Output is correct
2 Correct 49 ms 3284 KB Output is correct
3 Execution timed out 1089 ms 2888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 8276 KB Output is correct
2 Execution timed out 1093 ms 14660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 11408 KB Output is correct
2 Execution timed out 1096 ms 20488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 13004 KB Output is correct
2 Execution timed out 1084 ms 23320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 16096 KB Output is correct
2 Execution timed out 1085 ms 29264 KB Time limit exceeded
3 Halted 0 ms 0 KB -