oj.uz

Submission #974143

# Submission time Handle Problem Language Result Execution time Memory
974143 2024-05-02T23:10:14 Z AksLolCoding Mobile (BOI12_mobile) C++17
90 / 100
 1000 ms 49128 KB 
#include <bits/stdc++.h>
using namespace std;

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

const ld diff = 1e-5;
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 = 2e9, m;
	while (r - l > diff) {
		m = (r + l) / 2;
		if (check(m)) r = m;
		else l = m;
	}
	printf("%.5Lf\n", m);
}

Subtask #1
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 2 ms 544 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 5 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 5 ms 472 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 604 KB Output is correct
2 Correct 3 ms 708 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 5 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 6 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3384 KB Output is correct
2 Correct 45 ms 3932 KB Output is correct
3 Correct 35 ms 2756 KB Output is correct
4 Correct 92 ms 3992 KB Output is correct
5 Correct 40 ms 2416 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3544 KB Output is correct
2 Correct 65 ms 3308 KB Output is correct
3 Correct 77 ms 3920 KB Output is correct
4 Correct 81 ms 3924 KB Output is correct
5 Correct 95 ms 4572 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3676 KB Output is correct
2 Correct 45 ms 4184 KB Output is correct
3 Correct 54 ms 3932 KB Output is correct
4 Correct 113 ms 5456 KB Output is correct
5 Correct 86 ms 4176 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5144 KB Output is correct
2 Correct 54 ms 5000 KB Output is correct
3 Correct 62 ms 4616 KB Output is correct
4 Correct 113 ms 5548 KB Output is correct
5 Correct 98 ms 4840 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4944 KB Output is correct
2 Correct 65 ms 4996 KB Output is correct
3 Correct 69 ms 4692 KB Output is correct
4 Correct 113 ms 5536 KB Output is correct
5 Correct 100 ms 4700 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 20408 KB Output is correct
2 Correct 280 ms 23120 KB Output is correct
3 Correct 279 ms 22868 KB Output is correct
4 Correct 564 ms 25144 KB Output is correct
5 Correct 486 ms 22512 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 23904 KB Output is correct
2 Correct 472 ms 22256 KB Output is correct
3 Correct 319 ms 21428 KB Output is correct
4 Correct 561 ms 24660 KB Output is correct
5 Correct 505 ms 23152 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 24348 KB Output is correct
2 Correct 346 ms 27784 KB Output is correct
3 Correct 338 ms 27188 KB Output is correct
4 Correct 705 ms 29992 KB Output is correct
5 Correct 588 ms 26660 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 28496 KB Output is correct
2 Correct 562 ms 26152 KB Output is correct
3 Correct 393 ms 25884 KB Output is correct
4 Correct 693 ms 29988 KB Output is correct
5 Correct 634 ms 27408 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 28244 KB Output is correct
2 Correct 401 ms 32344 KB Output is correct
3 Correct 391 ms 31548 KB Output is correct
4 Correct 796 ms 34656 KB Output is correct
5 Correct 682 ms 30848 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 33236 KB Output is correct
2 Correct 637 ms 31172 KB Output is correct
3 Correct 451 ms 30032 KB Output is correct
4 Correct 794 ms 34728 KB Output is correct
5 Correct 705 ms 31704 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 32336 KB Output is correct
2 Correct 455 ms 36708 KB Output is correct
3 Correct 463 ms 36472 KB Output is correct
4 Correct 921 ms 39844 KB Output is correct
5 Correct 799 ms 35748 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 37968 KB Output is correct
2 Correct 735 ms 35236 KB Output is correct
3 Correct 524 ms 34228 KB Output is correct
4 Correct 920 ms 39492 KB Output is correct
5 Correct 821 ms 36296 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 39916 KB Output is correct
2 Correct 597 ms 45848 KB Output is correct
3 Correct 556 ms 44628 KB Output is correct
4 Execution timed out 1083 ms 48812 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 46724 KB Output is correct
2 Correct 934 ms 43940 KB Output is correct
3 Correct 666 ms 42580 KB Output is correct
4 Execution timed out 1034 ms 49128 KB Time limit exceeded
5 Halted 0 ms 0 KB -