Submission #593028

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593028	2022-07-10T08:34:01 Z	hail	Mobile (BOI12_mobile)	C++17	45 / 100	1000 ms	78636 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;
pld station[(int)1e6]{};

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

bool check_dist(ld r)
{
    pld ret_int;
    set<pld> intercepts;

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

    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;

    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	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	1 ms	212 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	468 KB	Output is correct
2	Correct	15 ms	536 KB	Output is correct
3	Correct	7 ms	468 KB	Output is correct
4	Correct	8 ms	468 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	720 KB	Output is correct
2	Correct	35 ms	716 KB	Output is correct
3	Correct	29 ms	620 KB	Output is correct
4	Correct	13 ms	712 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	712 KB	Output is correct
2	Correct	32 ms	716 KB	Output is correct
3	Correct	31 ms	716 KB	Output is correct
4	Correct	12 ms	716 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	708 KB	Output is correct
2	Correct	34 ms	596 KB	Output is correct
3	Correct	28 ms	716 KB	Output is correct
4	Correct	11 ms	596 KB	Output is correct
5	Correct	20 ms	580 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	313 ms	6156 KB	Output is correct
2	Correct	615 ms	7500 KB	Output is correct
3	Correct	319 ms	5124 KB	Output is correct
4	Correct	195 ms	7456 KB	Output is correct
5	Correct	193 ms	4168 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	322 ms	6460 KB	Output is correct
2	Correct	249 ms	6628 KB	Output is correct
3	Correct	250 ms	7688 KB	Output is correct
4	Correct	215 ms	7796 KB	Output is correct
5	Correct	192 ms	8548 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	787 ms	7116 KB	Output is correct
2	Correct	645 ms	7880 KB	Output is correct
3	Correct	531 ms	7932 KB	Output is correct
4	Correct	164 ms	10100 KB	Output is correct
5	Correct	333 ms	8200 KB	Output is correct

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	751 ms	8136 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	434 ms	8140 KB	Output is correct
2	Correct	852 ms	9548 KB	Output is correct
3	Correct	692 ms	9292 KB	Output is correct
4	Correct	163 ms	10008 KB	Output is correct
5	Correct	328 ms	9396 KB	Output is correct

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1101 ms	39372 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	1097 ms	39452 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	1099 ms	47180 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	1083 ms	47248 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	1093 ms	55056 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	1045 ms	55040 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	1100 ms	62808 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	1088 ms	62880 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	78508 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	1086 ms	78636 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #593028

Compilation message