Submission #754176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754176	2023-06-07T06:12:31 Z	lukehsiao	Mobile (BOI12_mobile)	C++14	8 / 100	1000 ms	32344 KB

mobile

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

const int mxN = 1e6;
ll n, L, x[mxN], y[mxN];

struct Range {
	double lo, hi;
	Range(double l, double r) : lo(l), hi(r) {};
	bool operator<(const Range &r) const {
		return hi < r.lo;
	}
	void merge(const Range &r) {
		lo = min(lo, r.lo);
		hi = max(hi, r.hi);
	}
};

bool works(double r) {
	set<Range> s;
	for (int i=0; i<n; ++i) {
		double d = r*r - y[i]*y[i];
		if (d >= 0) {
			Range rng = Range(x[i]-sqrt(d), x[i]+sqrt(d));
			auto it1 = s.lower_bound(rng);
			auto it2 = s.upper_bound(rng);
			while (it1 != it2) {
				rng.merge(*it1);
				it1 = s.erase(it1);
			}
			s.insert(rng);
		}
	}
	for (const Range &rng : s)
		if (rng.lo <= 0 && rng.hi >= L)
			return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> L;
	for (int i=0; i<n; ++i)
		cin >> x[i] >> y[i];
	
	double lo = 0, hi = 3e9;
	while (hi-lo > 1e-3) {
		double mid = (lo+hi)/2;
		if (works(mid))
			hi = mid;
		else
			lo = mid;
	}

	cout << (lo+hi)/2 << '\n';
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	340 KB	Output is correct
2	Correct	5 ms	400 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Incorrect	5 ms	340 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	456 KB	Output is correct
2	Incorrect	9 ms	472 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	340 KB	Output is correct
2	Incorrect	9 ms	464 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	468 KB	Output is correct
2	Incorrect	9 ms	412 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	2380 KB	Output is correct
2	Incorrect	139 ms	2636 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	2292 KB	Output is correct
2	Correct	63 ms	2120 KB	Output is correct
3	Incorrect	81 ms	2516 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	2324 KB	Output is correct
2	Incorrect	137 ms	2768 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	172 ms	3432 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	196 ms	3580 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	871 ms	12432 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	885 ms	16336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1025 ms	14956 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1051 ms	19656 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1058 ms	17312 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1059 ms	22768 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1050 ms	19744 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1055 ms	25956 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1061 ms	24608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1071 ms	32344 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #754176

Compilation message