Submission #1092980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1092980	2024-09-25T14:49:18 Z	TommasoUlian	Mobile (BOI12_mobile)	C++17	100 / 100	296 ms	35436 KB

mobile

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
 
#define all(x) x.begin(), x.end()
 
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int N;
	ll L;
	cin >> N >> L;
 
	vector<ll> X(N);
	vector<ll> Y(N);
	for (int i=0;i<N;i++) cin >> X[i] >> Y[i];
 
	auto get_hw = [&](double y, double r) {
		if (abs(y) > r - 1e-6) return -1.0;
		return sqrt((r-y) * (r+y));
	};
 
	auto can_do = [&](double R) {
		double progress = 0.;
		for (int i=0;i<N;i++) {
			double hw = get_hw((double)Y[i], R);
			if (hw < 0) continue;
 
			double l = (double)X[i] - hw;
			double r = (double)X[i] + hw;
			if (l <= progress + 1e-6) progress = max(progress, r);
			if (progress >= (double)L) return true;
		}
 
		return false;
	};
 
	double lo = 1;
	double hi = 2e9;
 
	while (hi - lo > 1e-4) {
		double mid = (lo + hi) / 2;
		if (can_do(mid)) hi = mid;
		else lo = mid;
	}
	cout << setprecision(18);
	cout << (lo + hi)/2 << endl;
 
	return 0;
}

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	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	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	344 KB	Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
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	604 KB	Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2256 KB	Output is correct
2	Correct	14 ms	2748 KB	Output is correct
3	Correct	8 ms	1884 KB	Output is correct
4	Correct	14 ms	2652 KB	Output is correct
5	Correct	6 ms	1624 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	2396 KB	Output is correct
2	Correct	12 ms	2396 KB	Output is correct
3	Correct	13 ms	2652 KB	Output is correct
4	Correct	14 ms	2720 KB	Output is correct
5	Correct	16 ms	3160 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	23 ms	2920 KB	Output is correct
3	Correct	13 ms	2760 KB	Output is correct
4	Correct	20 ms	3940 KB	Output is correct
5	Correct	13 ms	2652 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3420 KB	Output is correct
2	Correct	19 ms	3420 KB	Output is correct
3	Correct	15 ms	2924 KB	Output is correct
4	Correct	21 ms	3820 KB	Output is correct
5	Correct	16 ms	3164 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3572 KB	Output is correct
2	Correct	19 ms	3420 KB	Output is correct
3	Correct	14 ms	2908 KB	Output is correct
4	Correct	20 ms	3988 KB	Output is correct
5	Correct	17 ms	3164 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	12368 KB	Output is correct
2	Correct	108 ms	15444 KB	Output is correct
3	Correct	87 ms	15188 KB	Output is correct
4	Correct	103 ms	17040 KB	Output is correct
5	Correct	111 ms	14928 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	15952 KB	Output is correct
2	Correct	169 ms	14244 KB	Output is correct
3	Correct	79 ms	13904 KB	Output is correct
4	Correct	101 ms	17484 KB	Output is correct
5	Correct	83 ms	15580 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	14932 KB	Output is correct
2	Correct	102 ms	18388 KB	Output is correct
3	Correct	111 ms	18396 KB	Output is correct
4	Correct	121 ms	21588 KB	Output is correct
5	Correct	96 ms	17744 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	19028 KB	Output is correct
2	Correct	186 ms	16860 KB	Output is correct
3	Correct	108 ms	16500 KB	Output is correct
4	Correct	122 ms	21584 KB	Output is correct
5	Correct	106 ms	18540 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	155 ms	16980 KB	Output is correct
2	Correct	155 ms	21328 KB	Output is correct
3	Correct	122 ms	21332 KB	Output is correct
4	Correct	136 ms	24912 KB	Output is correct
5	Correct	119 ms	20308 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	21656 KB	Output is correct
2	Correct	219 ms	19980 KB	Output is correct
3	Correct	123 ms	19796 KB	Output is correct
4	Correct	144 ms	24596 KB	Output is correct
5	Correct	119 ms	21532 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	19284 KB	Output is correct
2	Correct	151 ms	24148 KB	Output is correct
3	Correct	150 ms	24364 KB	Output is correct
4	Correct	185 ms	28588 KB	Output is correct
5	Correct	138 ms	24016 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	24908 KB	Output is correct
2	Correct	239 ms	22608 KB	Output is correct
3	Correct	132 ms	22356 KB	Output is correct
4	Correct	165 ms	28236 KB	Output is correct
5	Correct	143 ms	24356 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	230 ms	23992 KB	Output is correct
2	Correct	170 ms	29984 KB	Output is correct
3	Correct	171 ms	30568 KB	Output is correct
4	Correct	196 ms	35156 KB	Output is correct
5	Correct	159 ms	29520 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	31144 KB	Output is correct
2	Correct	296 ms	27988 KB	Output is correct
3	Correct	151 ms	28244 KB	Output is correct
4	Correct	209 ms	35436 KB	Output is correct
5	Correct	170 ms	30668 KB	Output is correct

Submission #1092980

Compilation message