oj.uz

Submission #684608

# Submission time Handle Problem Language Result Execution time Memory
684608 2023-01-22T01:07:30 Z aaggupta07 Mobile (BOI12_mobile) C++17
100 / 100
 355 ms 17092 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 << '\n';
	return 0;
}

Subtask #1
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 1 ms 212 KB Output is correct
4 Correct 1 ms 332 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 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 1 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 388 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 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 408 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 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 460 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 27 ms 2248 KB Output is correct
2 Correct 25 ms 2308 KB Output is correct
3 Correct 15 ms 1688 KB Output is correct
4 Correct 23 ms 2316 KB Output is correct
5 Correct 13 ms 1492 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2256 KB Output is correct
2 Correct 20 ms 2228 KB Output is correct
3 Correct 30 ms 2488 KB Output is correct
4 Correct 23 ms 2400 KB Output is correct
5 Correct 25 ms 2564 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2336 KB Output is correct
2 Correct 27 ms 2476 KB Output is correct
3 Correct 25 ms 2432 KB Output is correct
4 Correct 31 ms 2636 KB Output is correct
5 Correct 23 ms 2468 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2560 KB Output is correct
2 Correct 31 ms 2696 KB Output is correct
3 Correct 27 ms 2864 KB Output is correct
4 Correct 29 ms 2556 KB Output is correct
5 Correct 26 ms 2636 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2640 KB Output is correct
2 Correct 32 ms 2692 KB Output is correct
3 Correct 28 ms 2688 KB Output is correct
4 Correct 30 ms 2508 KB Output is correct
5 Correct 26 ms 2472 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8904 KB Output is correct
2 Correct 157 ms 9528 KB Output is correct
3 Correct 156 ms 9764 KB Output is correct
4 Correct 136 ms 9592 KB Output is correct
5 Correct 125 ms 9020 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9312 KB Output is correct
2 Correct 196 ms 9288 KB Output is correct
3 Correct 126 ms 8944 KB Output is correct
4 Correct 135 ms 9136 KB Output is correct
5 Correct 126 ms 9004 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 10348 KB Output is correct
2 Correct 187 ms 10476 KB Output is correct
3 Correct 179 ms 10300 KB Output is correct
4 Correct 168 ms 10368 KB Output is correct
5 Correct 155 ms 10104 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 10088 KB Output is correct
2 Correct 233 ms 9992 KB Output is correct
3 Correct 154 ms 10084 KB Output is correct
4 Correct 155 ms 9712 KB Output is correct
5 Correct 152 ms 9804 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 11264 KB Output is correct
2 Correct 211 ms 11264 KB Output is correct
3 Correct 206 ms 11408 KB Output is correct
4 Correct 189 ms 11400 KB Output is correct
5 Correct 170 ms 11376 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 11180 KB Output is correct
2 Correct 261 ms 11264 KB Output is correct
3 Correct 183 ms 11212 KB Output is correct
4 Correct 182 ms 11156 KB Output is correct
5 Correct 201 ms 11332 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 12812 KB Output is correct
2 Correct 248 ms 12876 KB Output is correct
3 Correct 241 ms 12856 KB Output is correct
4 Correct 215 ms 13180 KB Output is correct
5 Correct 205 ms 13216 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 13132 KB Output is correct
2 Correct 298 ms 13220 KB Output is correct
3 Correct 217 ms 13320 KB Output is correct
4 Correct 212 ms 13184 KB Output is correct
5 Correct 204 ms 13200 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 16696 KB Output is correct
2 Correct 313 ms 16640 KB Output is correct
3 Correct 300 ms 16544 KB Output is correct
4 Correct 266 ms 16332 KB Output is correct
5 Correct 263 ms 17080 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 17092 KB Output is correct
2 Correct 355 ms 16968 KB Output is correct
3 Correct 271 ms 16944 KB Output is correct
4 Correct 272 ms 16592 KB Output is correct
5 Correct 251 ms 16936 KB Output is correct