Submission #477080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477080	2021-09-30T06:13:45 Z	qwerty1234	Mobile (BOI12_mobile)	C++17	100 / 100	747 ms	18200 KB

mobile

#include <bits/stdc++.h>

#define ll long long

using namespace std;

bool check(double maxDist, vector<pair<double, double>> &transceivers, ll N, ll L) {
	double covered = 0;
	for (int i = 0; i < N; i++) {
		double ySquared = transceivers[i].second * transceivers[i].second;
		double hypoSquared = maxDist * maxDist;
		if (hypoSquared - ySquared < 0) {
			continue;
		}
		double x = sqrt(hypoSquared - ySquared);
		if (transceivers[i].first - x <= covered) {
			covered = max(covered, transceivers[i].first + x);
		}
	}
	return covered >= L;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll N, L;
	cin >> N >> L;
	vector<pair<double, double>> transceivers(N);
	for (int i = 0; i < N; i++) cin >> transceivers[i].first >> transceivers[i].second;
	double l = 0;
	double r = 1e9;
	double ans = 0;
	while (r - l >= 0.001) {
		double mid = l + (r - l) / 2;
		// cout << l << ' ' << r << ' ' << mid << '\n';
		if (check(mid, transceivers, N, L)) {
			r = mid;
			ans = mid;
		} else {
			l = mid;
		}
	}
	printf("%0.4lf\n", ans);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	440 KB	Output is correct
2	Correct	4 ms	460 KB	Output is correct
3	Correct	3 ms	332 KB	Output is correct
4	Correct	4 ms	460 KB	Output is correct
5	Correct	4 ms	332 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	1988 KB	Output is correct
2	Correct	55 ms	1996 KB	Output is correct
3	Correct	37 ms	1608 KB	Output is correct
4	Correct	54 ms	1900 KB	Output is correct
5	Correct	30 ms	1484 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	1996 KB	Output is correct
2	Correct	43 ms	1920 KB	Output is correct
3	Correct	48 ms	2096 KB	Output is correct
4	Correct	59 ms	1996 KB	Output is correct
5	Correct	66 ms	2176 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	2124 KB	Output is correct
2	Correct	55 ms	2124 KB	Output is correct
3	Correct	52 ms	2076 KB	Output is correct
4	Correct	75 ms	2372 KB	Output is correct
5	Correct	53 ms	2124 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	2380 KB	Output is correct
2	Correct	66 ms	2344 KB	Output is correct
3	Correct	56 ms	2380 KB	Output is correct
4	Correct	76 ms	2380 KB	Output is correct
5	Correct	64 ms	2448 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	2380 KB	Output is correct
2	Correct	71 ms	2384 KB	Output is correct
3	Correct	62 ms	2376 KB	Output is correct
4	Correct	71 ms	2380 KB	Output is correct
5	Correct	63 ms	2344 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	8648 KB	Output is correct
2	Correct	380 ms	8816 KB	Output is correct
3	Correct	373 ms	8664 KB	Output is correct
4	Correct	361 ms	8648 KB	Output is correct
5	Correct	332 ms	8772 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	8652 KB	Output is correct
2	Correct	375 ms	8740 KB	Output is correct
3	Correct	299 ms	8644 KB	Output is correct
4	Correct	353 ms	8644 KB	Output is correct
5	Correct	316 ms	8772 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	331 ms	10188 KB	Output is correct
2	Correct	432 ms	10220 KB	Output is correct
3	Correct	418 ms	10188 KB	Output is correct
4	Correct	448 ms	10216 KB	Output is correct
5	Correct	376 ms	10308 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	433 ms	10212 KB	Output is correct
2	Correct	448 ms	10304 KB	Output is correct
3	Correct	351 ms	10188 KB	Output is correct
4	Correct	459 ms	10308 KB	Output is correct
5	Correct	394 ms	10224 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	412 ms	11776 KB	Output is correct
2	Correct	491 ms	11772 KB	Output is correct
3	Correct	499 ms	11972 KB	Output is correct
4	Correct	519 ms	11972 KB	Output is correct
5	Correct	451 ms	12100 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	497 ms	11724 KB	Output is correct
2	Correct	523 ms	11976 KB	Output is correct
3	Correct	422 ms	11904 KB	Output is correct
4	Correct	526 ms	11852 KB	Output is correct
5	Correct	438 ms	12128 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	462 ms	13260 KB	Output is correct
2	Correct	541 ms	13380 KB	Output is correct
3	Correct	539 ms	13516 KB	Output is correct
4	Correct	582 ms	13596 KB	Output is correct
5	Correct	496 ms	13596 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	578 ms	13380 KB	Output is correct
2	Correct	568 ms	13696 KB	Output is correct
3	Correct	473 ms	13636 KB	Output is correct
4	Correct	584 ms	13700 KB	Output is correct
5	Correct	499 ms	13636 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	585 ms	16472 KB	Output is correct
2	Correct	735 ms	17616 KB	Output is correct
3	Correct	668 ms	16736 KB	Output is correct
4	Correct	747 ms	16068 KB	Output is correct
5	Correct	621 ms	16836 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	718 ms	18200 KB	Output is correct
2	Correct	718 ms	16728 KB	Output is correct
3	Correct	644 ms	16672 KB	Output is correct
4	Correct	744 ms	15980 KB	Output is correct
5	Correct	626 ms	16584 KB	Output is correct

Submission #477080

Compilation message