oj.uz

답안 #593251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593251 2022-07-10T16:35:07 Z hail Mobile (BOI12_mobile) C++17
75 / 100
 1000 ms 21356 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)
{
    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;
}


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

    cout<<setprecision(20); 

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

    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=max_coor+l;
    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 396 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 404 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

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 1492 KB Output is correct
2 Correct 36 ms 1532 KB Output is correct
3 Correct 31 ms 1152 KB Output is correct
4 Correct 45 ms 1584 KB Output is correct
5 Correct 19 ms 1108 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 1492 KB Output is correct
2 Correct 33 ms 1364 KB Output is correct
3 Correct 38 ms 1492 KB Output is correct
4 Correct 41 ms 1492 KB Output is correct
5 Correct 51 ms 1696 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 1620 KB Output is correct
2 Correct 41 ms 1620 KB Output is correct
3 Correct 51 ms 1620 KB Output is correct
4 Correct 60 ms 1876 KB Output is correct
5 Correct 37 ms 1620 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1900 KB Output is correct
2 Correct 47 ms 3280 KB Output is correct
3 Correct 63 ms 2888 KB Output is correct
4 Correct 60 ms 3792 KB Output is correct
5 Correct 50 ms 3032 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 1904 KB Output is correct
2 Correct 46 ms 1900 KB Output is correct
3 Correct 61 ms 1904 KB Output is correct
4 Correct 60 ms 1876 KB Output is correct
5 Correct 46 ms 1876 KB Output is correct

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 8160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 8172 KB Output is correct
2 Correct 454 ms 8160 KB Output is correct
3 Correct 294 ms 8248 KB Output is correct
4 Correct 285 ms 8260 KB Output is correct
5 Correct 244 ms 8260 KB Output is correct

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 9736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 9684 KB Output is correct
2 Correct 492 ms 17644 KB Output is correct
3 Correct 373 ms 16588 KB Output is correct
4 Correct 358 ms 21356 KB Output is correct
5 Correct 297 ms 18528 KB Output is correct

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1079 ms 11292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 342 ms 11276 KB Output is correct
2 Correct 617 ms 11204 KB Output is correct
3 Correct 438 ms 11400 KB Output is correct
4 Correct 399 ms 11336 KB Output is correct
5 Correct 340 ms 11348 KB Output is correct

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1072 ms 12848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 12756 KB Output is correct
2 Correct 698 ms 12756 KB Output is correct
3 Correct 490 ms 12884 KB Output is correct
4 Correct 459 ms 12852 KB Output is correct
5 Correct 391 ms 12884 KB Output is correct

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 487 ms 15988 KB Output is correct
2 Correct 882 ms 15956 KB Output is correct
3 Correct 616 ms 16084 KB Output is correct
4 Correct 578 ms 16084 KB Output is correct
5 Correct 499 ms 15992 KB Output is correct