Submission #593251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593251	2022-07-10T16:35:07 Z	hail	Mobile (BOI12_mobile)	C++17	75 / 100	1000 ms	21356 KB

mobile

#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

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	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	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	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

Submission #593251

Compilation message