Submission #1042251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1042251	2024-08-02T17:45:24 Z	sssamui	Mobile (BOI12_mobile)	C++17	100 / 100	738 ms	35412 KB

mobile

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <iomanip>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	double L;
	cin >> n >> L;
	vector<pair<double, double>> xy(n);
	for (int i = 0; i < n; i++) cin >> xy[i].first >> xy[i].second;

	double l = 0, r = 1e9;
	int it = 60;
	while (it--)
	{
		double m = (l + r) / 2;
		stack<pair<double, double>> c;
		for (int i = 0; i < n; i++) if (xy[i].second * xy[i].second <= m * m)
		{
			double sq = sqrt(m * m - xy[i].second * xy[i].second);
			double a = fmax(0, xy[i].first - sq), b = fmin(L, xy[i].first + sq);
			if (a <= b)
			{
				while (!c.empty() && (c.top().second >= a))
				{
					a = fmin(a, c.top().first), b = fmax(b, c.top().second);
					c.pop();
				}

				c.push({ a, b });
			}
		}

		if ((c.size() != 1) || ((c.top().first > 0) || (c.top().second < L))) l = m;
		else r = m;
	}

	cout << fixed << setprecision(6) << l;
}

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	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 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	2 ms	348 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	1 ms	348 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	2 ms	348 KB	Output is correct
2	Correct	4 ms	600 KB	Output is correct
3	Correct	3 ms	572 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	1628 KB	Output is correct
2	Correct	67 ms	2672 KB	Output is correct
3	Correct	34 ms	1880 KB	Output is correct
4	Correct	29 ms	2652 KB	Output is correct
5	Correct	21 ms	1640 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	1640 KB	Output is correct
2	Correct	29 ms	2208 KB	Output is correct
3	Correct	32 ms	2756 KB	Output is correct
4	Correct	31 ms	2920 KB	Output is correct
5	Correct	32 ms	3172 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	1640 KB	Output is correct
2	Correct	59 ms	1640 KB	Output is correct
3	Correct	52 ms	1640 KB	Output is correct
4	Correct	36 ms	1896 KB	Output is correct
5	Correct	36 ms	2648 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	1884 KB	Output is correct
2	Correct	85 ms	1884 KB	Output is correct
3	Correct	61 ms	1884 KB	Output is correct
4	Correct	35 ms	1884 KB	Output is correct
5	Correct	39 ms	3160 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	1880 KB	Output is correct
2	Correct	72 ms	3416 KB	Output is correct
3	Correct	61 ms	3028 KB	Output is correct
4	Correct	36 ms	3940 KB	Output is correct
5	Correct	39 ms	3164 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	352 ms	8284 KB	Output is correct
2	Correct	366 ms	8284 KB	Output is correct
3	Correct	381 ms	8284 KB	Output is correct
4	Correct	168 ms	8280 KB	Output is correct
5	Correct	203 ms	14932 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	401 ms	8280 KB	Output is correct
2	Correct	338 ms	8284 KB	Output is correct
3	Correct	307 ms	14032 KB	Output is correct
4	Correct	189 ms	17492 KB	Output is correct
5	Correct	205 ms	15444 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	9820 KB	Output is correct
2	Correct	455 ms	9820 KB	Output is correct
3	Correct	448 ms	9820 KB	Output is correct
4	Correct	206 ms	9820 KB	Output is correct
5	Correct	236 ms	17636 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	9816 KB	Output is correct
2	Correct	389 ms	9820 KB	Output is correct
3	Correct	379 ms	16468 KB	Output is correct
4	Correct	234 ms	21484 KB	Output is correct
5	Correct	223 ms	18516 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	483 ms	11356 KB	Output is correct
2	Correct	512 ms	11356 KB	Output is correct
3	Correct	528 ms	11356 KB	Output is correct
4	Correct	249 ms	11356 KB	Output is correct
5	Correct	274 ms	20308 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	11352 KB	Output is correct
2	Correct	431 ms	11356 KB	Output is correct
3	Correct	472 ms	19588 KB	Output is correct
4	Correct	241 ms	24656 KB	Output is correct
5	Correct	268 ms	21512 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	565 ms	12888 KB	Output is correct
2	Correct	586 ms	12892 KB	Output is correct
3	Correct	600 ms	12892 KB	Output is correct
4	Correct	264 ms	12892 KB	Output is correct
5	Correct	308 ms	24148 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	585 ms	12888 KB	Output is correct
2	Correct	496 ms	12892 KB	Output is correct
3	Correct	498 ms	22432 KB	Output is correct
4	Correct	288 ms	28456 KB	Output is correct
5	Correct	306 ms	24480 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	688 ms	15964 KB	Output is correct
2	Correct	723 ms	15960 KB	Output is correct
3	Correct	738 ms	15960 KB	Output is correct
4	Correct	337 ms	15964 KB	Output is correct
5	Correct	406 ms	29520 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	727 ms	15964 KB	Output is correct
2	Correct	611 ms	16108 KB	Output is correct
3	Correct	635 ms	28396 KB	Output is correct
4	Correct	339 ms	35412 KB	Output is correct
5	Correct	371 ms	31060 KB	Output is correct

Submission #1042251

Compilation message