Submission #974145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
974145	2024-05-02T23:14:26 Z	AksLolCoding	Mobile (BOI12_mobile)	C++17	90 / 100	1000 ms	31772 KB

mobile

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

using ld = long double;
using ld2 = array<ld, 2>;

const ld diff = 5e-4;
int n;
ld h;
vector<ld2> pts;

ld2 range(ld dist, ld2& pt) {
	ld dx = sqrt(dist*dist - pt[1]*pt[1]);
	return {pt[0] - dx, pt[0] + dx};
}

bool check(ld dist) {
	ld left = 0;
	for (ld2& pt: pts) {
		ld2 r = range(dist, pt);
		if (r[0] <= left) left = max(left, r[1]);
	}
	return (left >= h);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> h;
	pts.resize(n);
	for (auto& i: pts) cin >> i[0] >> i[1];

	// solve
	ld l = 0, r = 1.5e9, m;
	while (r - l > diff) {
		m = (r + l) / 2;
		if (check(m)) r = m;
		else l = m;
	}
	printf("%.4Lf\n", m);
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	344 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	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	3 ms	600 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	2 ms	348 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	2652 KB	Output is correct
2	Correct	39 ms	2652 KB	Output is correct
3	Correct	33 ms	2140 KB	Output is correct
4	Correct	78 ms	2896 KB	Output is correct
5	Correct	36 ms	1884 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	2904 KB	Output is correct
2	Correct	58 ms	2652 KB	Output is correct
3	Correct	69 ms	2908 KB	Output is correct
4	Correct	74 ms	2928 KB	Output is correct
5	Correct	88 ms	3164 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	3164 KB	Output is correct
2	Correct	43 ms	2908 KB	Output is correct
3	Correct	60 ms	3104 KB	Output is correct
4	Correct	103 ms	3420 KB	Output is correct
5	Correct	76 ms	3244 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	3416 KB	Output is correct
2	Correct	54 ms	3588 KB	Output is correct
3	Correct	58 ms	3420 KB	Output is correct
4	Correct	105 ms	3420 KB	Output is correct
5	Correct	88 ms	3588 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	3416 KB	Output is correct
2	Correct	59 ms	3416 KB	Output is correct
3	Correct	59 ms	3416 KB	Output is correct
4	Correct	103 ms	3420 KB	Output is correct
5	Correct	94 ms	3416 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	252 ms	15964 KB	Output is correct
2	Correct	276 ms	15964 KB	Output is correct
3	Correct	262 ms	15960 KB	Output is correct
4	Correct	517 ms	16112 KB	Output is correct
5	Correct	437 ms	15964 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	286 ms	16208 KB	Output is correct
2	Correct	398 ms	16112 KB	Output is correct
3	Correct	298 ms	15960 KB	Output is correct
4	Correct	506 ms	15964 KB	Output is correct
5	Correct	458 ms	16116 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	317 ms	19280 KB	Output is correct
2	Correct	322 ms	19240 KB	Output is correct
3	Correct	323 ms	19440 KB	Output is correct
4	Correct	624 ms	19032 KB	Output is correct
5	Correct	534 ms	19244 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	358 ms	19032 KB	Output is correct
2	Correct	483 ms	19036 KB	Output is correct
3	Correct	380 ms	19240 KB	Output is correct
4	Correct	627 ms	19240 KB	Output is correct
5	Correct	543 ms	19032 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	359 ms	22380 KB	Output is correct
2	Correct	382 ms	22368 KB	Output is correct
3	Correct	381 ms	22364 KB	Output is correct
4	Correct	722 ms	22372 KB	Output is correct
5	Correct	628 ms	22372 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	388 ms	22360 KB	Output is correct
2	Correct	593 ms	22376 KB	Output is correct
3	Correct	421 ms	22376 KB	Output is correct
4	Correct	719 ms	22608 KB	Output is correct
5	Correct	637 ms	22376 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	393 ms	25436 KB	Output is correct
2	Correct	432 ms	25512 KB	Output is correct
3	Correct	474 ms	25432 KB	Output is correct
4	Correct	825 ms	25680 KB	Output is correct
5	Correct	716 ms	25504 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	431 ms	25756 KB	Output is correct
2	Correct	691 ms	25500 KB	Output is correct
3	Correct	516 ms	25680 KB	Output is correct
4	Correct	824 ms	25504 KB	Output is correct
5	Correct	723 ms	25512 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	519 ms	31768 KB	Output is correct
2	Correct	550 ms	31768 KB	Output is correct
3	Correct	572 ms	31764 KB	Output is correct
4	Execution timed out	1029 ms	31768 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	545 ms	31764 KB	Output is correct
2	Correct	788 ms	31772 KB	Output is correct
3	Correct	598 ms	31768 KB	Output is correct
4	Execution timed out	1038 ms	31764 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Submission #974145

Compilation message