oj.uz

Submission #684607

# Submission time Handle Problem Language Result Execution time Memory
684607 2023-01-22T01:06:42 Z aaggupta07 Mobile (BOI12_mobile) C++17
100 / 100
 364 ms 22740 KB 
// Source: https://usaco.guide/general/io

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

#define int long long
#define f first
#define s second
#define mp make_pair

constexpr int MAX_C = 1.5e9;
constexpr int MAX_N = 1e6;

using pi = pair<int, int>;
using pd = pair<double, double>;

int n, l;
pi towers[MAX_N];

bool check(double p) {
	// cout << "Called: " << p << endl;

	double best = 0;
	for(int i = 0; i < n; ++i) {
		if(abs(towers[i].s) >= p) continue;
		double dist = sqrt(p * p - towers[i].s * towers[i].s);
		double d1 = towers[i].f - dist, d2 = towers[i].f + dist;
		if(d1 <= best) best = max(best, d2);
	}

	if(best > l) return true;
	return false;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> towers[i].f >> towers[i].s;
	
	double le = 1e-4, r = MAX_C;
	while(r - le >= 1e-3) {
		double mid = (le + r) / 2;
		if(check(mid)) r = mid;
		else le = mid;
	}

	cout.precision(4);
	cout << fixed << le;
	return 0;
}

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 1 ms 324 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 212 KB Output is correct
3 Correct 1 ms 340 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 348 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 340 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 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 468 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 3 ms 476 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 468 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 468 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 420 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 35 ms 1496 KB Output is correct
2 Correct 25 ms 2524 KB Output is correct
3 Correct 16 ms 1748 KB Output is correct
4 Correct 21 ms 2644 KB Output is correct
5 Correct 17 ms 1376 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1492 KB Output is correct
2 Correct 19 ms 2108 KB Output is correct
3 Correct 26 ms 2616 KB Output is correct
4 Correct 24 ms 2808 KB Output is correct
5 Correct 25 ms 3040 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1620 KB Output is correct
2 Correct 29 ms 1620 KB Output is correct
3 Correct 28 ms 1740 KB Output is correct
4 Correct 38 ms 3804 KB Output is correct
5 Correct 31 ms 2588 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1828 KB Output is correct
2 Correct 40 ms 2112 KB Output is correct
3 Correct 29 ms 2124 KB Output is correct
4 Correct 30 ms 3752 KB Output is correct
5 Correct 35 ms 3120 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1792 KB Output is correct
2 Correct 35 ms 2076 KB Output is correct
3 Correct 33 ms 2128 KB Output is correct
4 Correct 39 ms 3752 KB Output is correct
5 Correct 34 ms 3136 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8352 KB Output is correct
2 Correct 172 ms 8504 KB Output is correct
3 Correct 168 ms 8704 KB Output is correct
4 Correct 146 ms 8732 KB Output is correct
5 Correct 143 ms 13004 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 8768 KB Output is correct
2 Correct 201 ms 8788 KB Output is correct
3 Correct 173 ms 12936 KB Output is correct
4 Correct 144 ms 13108 KB Output is correct
5 Correct 143 ms 12968 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 10188 KB Output is correct
2 Correct 189 ms 10484 KB Output is correct
3 Correct 211 ms 14712 KB Output is correct
4 Correct 196 ms 14808 KB Output is correct
5 Correct 181 ms 14792 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 10756 KB Output is correct
2 Correct 233 ms 16332 KB Output is correct
3 Correct 167 ms 14960 KB Output is correct
4 Correct 188 ms 14948 KB Output is correct
5 Correct 190 ms 15036 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 12272 KB Output is correct
2 Correct 253 ms 12568 KB Output is correct
3 Correct 264 ms 16608 KB Output is correct
4 Correct 229 ms 16520 KB Output is correct
5 Correct 209 ms 16396 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 12760 KB Output is correct
2 Correct 270 ms 18024 KB Output is correct
3 Correct 226 ms 16576 KB Output is correct
4 Correct 204 ms 16644 KB Output is correct
5 Correct 212 ms 17760 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 14500 KB Output is correct
2 Correct 275 ms 14340 KB Output is correct
3 Correct 289 ms 18208 KB Output is correct
4 Correct 255 ms 18132 KB Output is correct
5 Correct 238 ms 18212 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 14496 KB Output is correct
2 Correct 309 ms 19616 KB Output is correct
3 Correct 224 ms 18256 KB Output is correct
4 Correct 258 ms 18228 KB Output is correct
5 Correct 216 ms 18112 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 17744 KB Output is correct
2 Correct 320 ms 17484 KB Output is correct
3 Correct 327 ms 22608 KB Output is correct
4 Correct 268 ms 16748 KB Output is correct
5 Correct 304 ms 22368 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 17452 KB Output is correct
2 Correct 364 ms 22740 KB Output is correct
3 Correct 281 ms 22444 KB Output is correct
4 Correct 280 ms 16848 KB Output is correct
5 Correct 264 ms 22028 KB Output is correct