Submission #670686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670686	2022-12-09T20:51:40 Z	thiago_bastos	Mobile (BOI12_mobile)	C++17	100 / 100	439 ms	23624 KB

mobile

#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 1e6 + 10;
int n, l;
ii pt[N];

bool evaluate(double d) {
	double last = 0;
	for(int i = 0; i < n; ++i) {
		auto [x, y] = pt[i];
		if(abs(y) > d) continue;
		double z = sqrt(d * d - (i64)y * y);
		if(max(0.0, x - z) <= last) last = max(last, min(l + 0.0, x + z));
	}
	return last >= l;
}

void solve() {
	cin >> n >> l;
	for(int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		pt[i] = {x, y};
	}
	sort(pt, pt + n);
	double lo = 0, hi = 2 * INF;	
	for(int i = 0; i < 45; ++i) {
		double m = (lo + hi) / 2;
		if(evaluate(m)) hi = m;
		else lo = m;
	}
	cout << fixed << setprecision(9) << hi << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	212 KB	Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	852 KB	Output is correct
2	Correct	26 ms	852 KB	Output is correct
3	Correct	17 ms	1284 KB	Output is correct
4	Correct	22 ms	2040 KB	Output is correct
5	Correct	14 ms	1040 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	940 KB	Output is correct
2	Correct	20 ms	756 KB	Output is correct
3	Correct	23 ms	964 KB	Output is correct
4	Correct	22 ms	836 KB	Output is correct
5	Correct	33 ms	988 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	980 KB	Output is correct
2	Correct	28 ms	940 KB	Output is correct
3	Correct	27 ms	1852 KB	Output is correct
4	Correct	30 ms	3036 KB	Output is correct
5	Correct	26 ms	1928 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	1108 KB	Output is correct
2	Correct	35 ms	2380 KB	Output is correct
3	Correct	32 ms	2116 KB	Output is correct
4	Correct	30 ms	2996 KB	Output is correct
5	Correct	31 ms	2324 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	1032 KB	Output is correct
2	Correct	36 ms	1092 KB	Output is correct
3	Correct	31 ms	2000 KB	Output is correct
4	Correct	29 ms	2928 KB	Output is correct
5	Correct	32 ms	2260 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	4216 KB	Output is correct
2	Correct	177 ms	11892 KB	Output is correct
3	Correct	185 ms	11432 KB	Output is correct
4	Correct	154 ms	13748 KB	Output is correct
5	Correct	147 ms	11112 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	4216 KB	Output is correct
2	Correct	227 ms	10816 KB	Output is correct
3	Correct	149 ms	9872 KB	Output is correct
4	Correct	142 ms	13516 KB	Output is correct
5	Correct	144 ms	11396 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	189 ms	5036 KB	Output is correct
2	Correct	211 ms	14244 KB	Output is correct
3	Correct	213 ms	13700 KB	Output is correct
4	Correct	177 ms	16948 KB	Output is correct
5	Correct	171 ms	12876 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	5012 KB	Output is correct
2	Correct	278 ms	12928 KB	Output is correct
3	Correct	186 ms	11748 KB	Output is correct
4	Correct	176 ms	16724 KB	Output is correct
5	Correct	183 ms	13700 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	5744 KB	Output is correct
2	Correct	248 ms	16616 KB	Output is correct
3	Correct	255 ms	15820 KB	Output is correct
4	Correct	199 ms	19240 KB	Output is correct
5	Correct	198 ms	14744 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	5784 KB	Output is correct
2	Correct	299 ms	15024 KB	Output is correct
3	Correct	216 ms	14156 KB	Output is correct
4	Correct	208 ms	19192 KB	Output is correct
5	Correct	196 ms	15864 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	247 ms	6732 KB	Output is correct
2	Correct	287 ms	19024 KB	Output is correct
3	Correct	294 ms	18184 KB	Output is correct
4	Correct	235 ms	22240 KB	Output is correct
5	Correct	230 ms	17616 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	279 ms	6800 KB	Output is correct
2	Correct	342 ms	17100 KB	Output is correct
3	Correct	256 ms	16192 KB	Output is correct
4	Correct	241 ms	22016 KB	Output is correct
5	Correct	223 ms	18096 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	8324 KB	Output is correct
2	Correct	362 ms	23624 KB	Output is correct
3	Correct	357 ms	22592 KB	Output is correct
4	Correct	281 ms	8652 KB	Output is correct
5	Correct	293 ms	21780 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	8136 KB	Output is correct
2	Correct	439 ms	21284 KB	Output is correct
3	Correct	326 ms	20372 KB	Output is correct
4	Correct	279 ms	8652 KB	Output is correct
5	Correct	293 ms	22856 KB	Output is correct

Submission #670686

Compilation message