oj.uz

Submission #593068

# Submission time Handle Problem Language Result Execution time Memory
593068 2022-07-10T10:49:09 Z hail Mobile (BOI12_mobile) C++17
45 / 100
 1000 ms 48296 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;
    vector<pld> intercepts;

    for(int j=0; j<n; j++)
    {
        pld i=station[j];    
        ret_int = intercept(i, r);
        if(ret_int.second<0 || ret_int.first>l) continue;
        else intercepts.push_back(ret_int);
    }

    sort(intercepts.begin(), intercepts.end());

    ld start=0;

    for(auto i: intercepts)
    {
        if(i.first>start) return false;
        else start= max(start, i.second);
        if(start>=l) return true;
    }

    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 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 5 ms 456 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 660 KB Output is correct
2 Correct 13 ms 832 KB Output is correct
3 Correct 18 ms 656 KB Output is correct
4 Correct 8 ms 708 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 660 KB Output is correct
2 Correct 14 ms 676 KB Output is correct
3 Correct 15 ms 660 KB Output is correct
4 Correct 7 ms 676 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 660 KB Output is correct
2 Correct 13 ms 684 KB Output is correct
3 Correct 16 ms 644 KB Output is correct
4 Correct 7 ms 692 KB Output is correct
5 Correct 10 ms 644 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 4864 KB Output is correct
2 Correct 309 ms 4988 KB Output is correct
3 Correct 165 ms 3168 KB Output is correct
4 Correct 119 ms 4876 KB Output is correct
5 Correct 102 ms 3056 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 4984 KB Output is correct
2 Correct 134 ms 4724 KB Output is correct
3 Correct 147 ms 5060 KB Output is correct
4 Correct 121 ms 4980 KB Output is correct
5 Correct 115 ms 5200 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 5300 KB Output is correct
2 Correct 331 ms 5100 KB Output is correct
3 Correct 362 ms 5168 KB Output is correct
4 Correct 105 ms 5688 KB Output is correct
5 Correct 174 ms 5316 KB Output is correct

Subtask #10
0 / 5.0

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

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 5620 KB Output is correct
2 Correct 441 ms 5660 KB Output is correct
3 Correct 489 ms 5664 KB Output is correct
4 Correct 109 ms 5568 KB Output is correct
5 Correct 175 ms 5664 KB Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 38908 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 1094 ms 39004 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 1092 ms 42112 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 1084 ms 42192 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 1090 ms 48296 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 1088 ms 48100 KB Time limit exceeded
2 Halted 0 ms 0 KB -