Submission #965001

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965001	2024-04-18T02:49:38 Z	pcc	Mobile (BOI12_mobile)	C++17	35 / 100	1000 ms	81576 KB

mobile

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ld long double
#define pld pair<ld,ld>

const int mxn = 1e6+10;
ll N,L;
pair<ll,ll> arr[mxn];

inline bool check(ld r){
	vector<pld> v;
	for(int i = 0;i<N;i++){
		if(r<abs(arr[i].sc))continue;
		v.push_back(pld(arr[i].fs-sqrt(r*r-arr[i].sc*arr[i].sc),arr[i].fs+sqrt(r*r-arr[i].sc*arr[i].sc)));
	}
	sort(v.begin(),v.end());
	ld pre = 0;
	for(auto &i:v){
		if(pre>L)return true;
		if(pre<i.fs)return false;
		pre = max(pre,i.sc);
	}
	return pre>L;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ld l = 0,r = 2e9;
	cin>>N>>L;
	for(int i = 0;i<N;i++)cin>>arr[i].fs>>arr[i].sc;
	for(int i = 0;i<100;i++){
		ld mid = (l+r)/2;
		if(check(mid))r = mid;
		else l = mid;
	}
	cout<<fixed<<setprecision(10)<<l<<'\n';
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	712 KB	Output is correct
2	Correct	17 ms	744 KB	Output is correct
3	Correct	5 ms	604 KB	Output is correct
4	Correct	17 ms	744 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1064 KB	Output is correct
2	Correct	35 ms	1032 KB	Output is correct
3	Correct	53 ms	1012 KB	Output is correct
4	Correct	11 ms	1204 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	996 KB	Output is correct
2	Correct	42 ms	1028 KB	Output is correct
3	Correct	50 ms	1000 KB	Output is correct
4	Correct	9 ms	1028 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	1016 KB	Output is correct
2	Correct	35 ms	1036 KB	Output is correct
3	Correct	57 ms	1012 KB	Output is correct
4	Correct	11 ms	1072 KB	Output is correct
5	Correct	13 ms	984 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	312 ms	11200 KB	Output is correct
2	Correct	907 ms	10568 KB	Output is correct
3	Correct	642 ms	7084 KB	Output is correct
4	Correct	155 ms	11520 KB	Output is correct
5	Correct	149 ms	6736 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	229 ms	10844 KB	Output is correct
2	Correct	179 ms	10012 KB	Output is correct
3	Correct	214 ms	11264 KB	Output is correct
4	Correct	154 ms	10504 KB	Output is correct
5	Correct	151 ms	10988 KB	Output is correct

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	759 ms	10456 KB	Output is correct
2	Execution timed out	1008 ms	10588 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	788 ms	12488 KB	Output is correct
2	Execution timed out	1049 ms	12484 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1033 ms	45284 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	1033 ms	49156 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	1032 ms	65572 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	1028 ms	71488 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	1049 ms	69596 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	1046 ms	73568 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	1093 ms	71164 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	1030 ms	76868 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	1038 ms	74480 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	1022 ms	81576 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #965001

Compilation message