Submission #1079736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1079736	2024-08-28T23:26:38 Z	EmmaXII	Mobile (BOI12_mobile)	C++17	100 / 100	282 ms	35184 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	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 #3
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	536 KB	Output is correct
4	Correct	1 ms	344 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	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 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	1624 KB	Output is correct
2	Correct	13 ms	1672 KB	Output is correct
3	Correct	8 ms	1312 KB	Output is correct
4	Correct	13 ms	1652 KB	Output is correct
5	Correct	7 ms	1116 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1692 KB	Output is correct
2	Correct	11 ms	1372 KB	Output is correct
3	Correct	13 ms	1628 KB	Output is correct
4	Correct	14 ms	1716 KB	Output is correct
5	Correct	16 ms	1628 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1628 KB	Output is correct
2	Correct	15 ms	1756 KB	Output is correct
3	Correct	13 ms	1628 KB	Output is correct
4	Correct	20 ms	2028 KB	Output is correct
5	Correct	12 ms	1624 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2040 KB	Output is correct
2	Correct	20 ms	3236 KB	Output is correct
3	Correct	17 ms	2912 KB	Output is correct
4	Correct	22 ms	3932 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	23 ms	1884 KB	Output is correct
2	Correct	19 ms	1884 KB	Output is correct
3	Correct	14 ms	1880 KB	Output is correct
4	Correct	22 ms	1884 KB	Output is correct
5	Correct	16 ms	1884 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	8280 KB	Output is correct
2	Correct	88 ms	8284 KB	Output is correct
3	Correct	81 ms	15312 KB	Output is correct
4	Correct	106 ms	17620 KB	Output is correct
5	Correct	82 ms	14932 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	8280 KB	Output is correct
2	Correct	158 ms	8528 KB	Output is correct
3	Correct	75 ms	8284 KB	Output is correct
4	Correct	96 ms	8284 KB	Output is correct
5	Correct	83 ms	8280 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	9820 KB	Output is correct
2	Correct	101 ms	9820 KB	Output is correct
3	Correct	97 ms	18512 KB	Output is correct
4	Correct	128 ms	21592 KB	Output is correct
5	Correct	101 ms	17748 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	9820 KB	Output is correct
2	Correct	199 ms	17748 KB	Output is correct
3	Correct	98 ms	16464 KB	Output is correct
4	Correct	148 ms	21332 KB	Output is correct
5	Correct	100 ms	18548 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	11356 KB	Output is correct
2	Correct	127 ms	11412 KB	Output is correct
3	Correct	132 ms	21388 KB	Output is correct
4	Correct	147 ms	24916 KB	Output is correct
5	Correct	109 ms	20380 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	11352 KB	Output is correct
2	Correct	216 ms	11356 KB	Output is correct
3	Correct	107 ms	11352 KB	Output is correct
4	Correct	129 ms	11356 KB	Output is correct
5	Correct	111 ms	11352 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	12892 KB	Output is correct
2	Correct	136 ms	12892 KB	Output is correct
3	Correct	152 ms	24660 KB	Output is correct
4	Correct	165 ms	28496 KB	Output is correct
5	Correct	138 ms	23888 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	12892 KB	Output is correct
2	Correct	236 ms	12888 KB	Output is correct
3	Correct	127 ms	12892 KB	Output is correct
4	Correct	153 ms	12888 KB	Output is correct
5	Correct	137 ms	12892 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	209 ms	16112 KB	Output is correct
2	Correct	152 ms	15964 KB	Output is correct
3	Correct	181 ms	30444 KB	Output is correct
4	Correct	205 ms	35184 KB	Output is correct
5	Correct	166 ms	29776 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	232 ms	16108 KB	Output is correct
2	Correct	282 ms	15960 KB	Output is correct
3	Correct	150 ms	15960 KB	Output is correct
4	Correct	201 ms	15964 KB	Output is correct
5	Correct	166 ms	15964 KB	Output is correct

Submission #1079736

Compilation message