oj.uz

Submission #754183

# Submission time Handle Problem Language Result Execution time Memory
754183 2023-06-07T06:31:54 Z lukehsiao Mobile (BOI12_mobile) C++14
100 / 100
 362 ms 35232 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

bool works(double r) {
	double cur = 0;
	for (int i=0; i<n; ++i) {
		double d = r*r - y[i]*y[i];
		if (d >= 0) {
			double del = sqrt(d);
			if (x[i]-del <= cur)
				cur = max(cur, x[i]+del);
		}
	}
	return cur >= L;
}

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 << fixed << setprecision(4) << (lo+hi)/2 << '\n';
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2164 KB Output is correct
2 Correct 39 ms 2596 KB Output is correct
3 Correct 14 ms 1740 KB Output is correct
4 Correct 32 ms 2668 KB Output is correct
5 Correct 11 ms 1516 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2264 KB Output is correct
2 Correct 19 ms 2244 KB Output is correct
3 Correct 21 ms 2636 KB Output is correct
4 Correct 21 ms 2732 KB Output is correct
5 Correct 26 ms 3152 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2360 KB Output is correct
2 Correct 23 ms 2696 KB Output is correct
3 Correct 22 ms 2528 KB Output is correct
4 Correct 27 ms 3816 KB Output is correct
5 Correct 21 ms 2640 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3188 KB Output is correct
2 Correct 32 ms 3264 KB Output is correct
3 Correct 25 ms 2900 KB Output is correct
4 Correct 34 ms 3840 KB Output is correct
5 Correct 24 ms 3012 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3176 KB Output is correct
2 Correct 34 ms 3288 KB Output is correct
3 Correct 25 ms 2908 KB Output is correct
4 Correct 28 ms 3796 KB Output is correct
5 Correct 26 ms 3172 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 9552 KB Output is correct
2 Correct 169 ms 15812 KB Output is correct
3 Correct 147 ms 15380 KB Output is correct
4 Correct 144 ms 17616 KB Output is correct
5 Correct 138 ms 14964 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 9508 KB Output is correct
2 Correct 216 ms 14760 KB Output is correct
3 Correct 120 ms 13832 KB Output is correct
4 Correct 136 ms 17480 KB Output is correct
5 Correct 126 ms 15460 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 11004 KB Output is correct
2 Correct 174 ms 19000 KB Output is correct
3 Correct 174 ms 18348 KB Output is correct
4 Correct 163 ms 21580 KB Output is correct
5 Correct 158 ms 17720 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 10996 KB Output is correct
2 Correct 246 ms 17756 KB Output is correct
3 Correct 213 ms 16560 KB Output is correct
4 Correct 164 ms 21572 KB Output is correct
5 Correct 149 ms 18440 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 12684 KB Output is correct
2 Correct 215 ms 22132 KB Output is correct
3 Correct 203 ms 21424 KB Output is correct
4 Correct 202 ms 24748 KB Output is correct
5 Correct 181 ms 20312 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 12820 KB Output is correct
2 Correct 272 ms 20532 KB Output is correct
3 Correct 177 ms 19660 KB Output is correct
4 Correct 201 ms 24672 KB Output is correct
5 Correct 196 ms 21480 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 14628 KB Output is correct
2 Correct 250 ms 25204 KB Output is correct
3 Correct 255 ms 24416 KB Output is correct
4 Correct 227 ms 28552 KB Output is correct
5 Correct 240 ms 24004 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 14900 KB Output is correct
2 Correct 297 ms 23420 KB Output is correct
3 Correct 204 ms 22368 KB Output is correct
4 Correct 244 ms 28284 KB Output is correct
5 Correct 204 ms 24444 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 18396 KB Output is correct
2 Correct 299 ms 31512 KB Output is correct
3 Correct 289 ms 30564 KB Output is correct
4 Correct 315 ms 35176 KB Output is correct
5 Correct 281 ms 29572 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 16184 KB Output is correct
2 Correct 362 ms 29216 KB Output is correct
3 Correct 270 ms 28236 KB Output is correct
4 Correct 284 ms 35232 KB Output is correct
5 Correct 262 ms 30608 KB Output is correct