Submission #1073886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1073886	2024-08-25T01:54:08 Z	vjudge1	Mobile (BOI12_mobile)	C++17	40 / 100	1000 ms	80940 KB

mobile

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

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

	int n;
	ld L;
	cin >> n >> L;
	vector <pair<ld,ld>> pts(n);
	for(int i=0; i<n; i++){
		cin >> pts[i].first >> pts[i].second;
	}

	const ld EPS = 1e-4;
	ld l=0, r=1e10, mid;
	while(r-l>EPS){
		mid = (l+r)/2;

		vector <pair<ld,ld>> seg;

		for(int i=0; i<n; i++){
			ld x = pts[i].first, y = pts[i].second;
			if(mid <= y){
				continue;
			}
			ld d = sqrt(mid*mid-y*y);
			if(x-d <= L && x+d >= 0)
				seg.push_back({max((ld)0.0, x-d),min((ld)L, x+d)});
		}

		sort(seg.begin(), seg.end());
		vector <pair<ld,ld>> processed;
		for(auto [start,end] : seg){
			if(!processed.empty() && start<=processed.back().second){
				processed.back().second = max(processed.back().second, end);
			}
			else{
				processed.push_back({start, end});
			}
		}

		bool can = false;
		if(processed.size() == 1){
			auto [x,y] = processed[0];
			if(abs(x) < EPS && abs(y-L) < EPS){
				can = true;
			}
		}
		if(can) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(6) << l << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	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	11 ms	796 KB	Output is correct
2	Correct	14 ms	792 KB	Output is correct
3	Correct	7 ms	604 KB	Output is correct
4	Correct	6 ms	784 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1096 KB	Output is correct
2	Correct	25 ms	1124 KB	Output is correct
3	Correct	32 ms	1088 KB	Output is correct
4	Correct	16 ms	1152 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1096 KB	Output is correct
2	Correct	29 ms	1128 KB	Output is correct
3	Correct	32 ms	1096 KB	Output is correct
4	Correct	15 ms	1112 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1096 KB	Output is correct
2	Correct	25 ms	1372 KB	Output is correct
3	Correct	34 ms	1152 KB	Output is correct
4	Correct	13 ms	1120 KB	Output is correct
5	Correct	21 ms	1092 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	11544 KB	Output is correct
2	Correct	594 ms	11248 KB	Output is correct
3	Correct	374 ms	6392 KB	Output is correct
4	Correct	267 ms	10260 KB	Output is correct
5	Correct	244 ms	6064 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	408 ms	11984 KB	Output is correct
2	Correct	323 ms	11164 KB	Output is correct
3	Correct	337 ms	10668 KB	Output is correct
4	Correct	277 ms	10316 KB	Output is correct
5	Correct	252 ms	11012 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	731 ms	12044 KB	Output is correct
2	Correct	653 ms	11976 KB	Output is correct
3	Correct	837 ms	11036 KB	Output is correct
4	Correct	226 ms	12088 KB	Output is correct
5	Correct	419 ms	11764 KB	Output is correct

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	653 ms	11932 KB	Output is correct
2	Correct	790 ms	12908 KB	Output is correct
3	Execution timed out	1058 ms	11568 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	310 ms	11812 KB	Output is correct
2	Correct	789 ms	12412 KB	Output is correct
3	Execution timed out	1014 ms	12552 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1031 ms	50488 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	1055 ms	48304 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	1022 ms	68468 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	1096 ms	68512 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	1081 ms	71608 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	1039 ms	71628 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	1067 ms	75864 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	1086 ms	75280 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	1073 ms	80896 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	1026 ms	80940 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #1073886

Compilation message