oj.uz

Submission #687266

# Submission time Handle Problem Language Result Execution time Memory
687266 2023-01-26T08:34:55 Z vjudge1 Mobile (BOI12_mobile) C++17
100 / 100
 407 ms 20784 KB 
#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 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 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 324 KB Output is correct
3 Correct 1 ms 328 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 2 ms 356 KB Output is correct
2 Correct 2 ms 368 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 3 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 3 ms 408 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 464 KB Output is correct
3 Correct 2 ms 340 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 4 ms 468 KB Output is correct
4 Correct 2 ms 412 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 28 ms 2280 KB Output is correct
2 Correct 25 ms 1760 KB Output is correct
3 Correct 15 ms 1364 KB Output is correct
4 Correct 21 ms 1684 KB Output is correct
5 Correct 12 ms 1364 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2304 KB Output is correct
2 Correct 19 ms 1584 KB Output is correct
3 Correct 21 ms 1748 KB Output is correct
4 Correct 21 ms 1744 KB Output is correct
5 Correct 23 ms 1920 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2380 KB Output is correct
2 Correct 36 ms 2680 KB Output is correct
3 Correct 24 ms 1884 KB Output is correct
4 Correct 29 ms 3772 KB Output is correct
5 Correct 23 ms 2632 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3356 KB Output is correct
2 Correct 29 ms 2132 KB Output is correct
3 Correct 26 ms 2892 KB Output is correct
4 Correct 30 ms 3840 KB Output is correct
5 Correct 26 ms 3016 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3372 KB Output is correct
2 Correct 45 ms 3276 KB Output is correct
3 Correct 28 ms 2844 KB Output is correct
4 Correct 28 ms 3808 KB Output is correct
5 Correct 26 ms 3144 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12428 KB Output is correct
2 Correct 163 ms 12748 KB Output is correct
3 Correct 169 ms 12752 KB Output is correct
4 Correct 159 ms 12904 KB Output is correct
5 Correct 134 ms 12844 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 12804 KB Output is correct
2 Correct 202 ms 12868 KB Output is correct
3 Correct 146 ms 12812 KB Output is correct
4 Correct 138 ms 12872 KB Output is correct
5 Correct 129 ms 12924 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 14440 KB Output is correct
2 Correct 218 ms 14444 KB Output is correct
3 Correct 208 ms 14412 KB Output is correct
4 Correct 172 ms 14436 KB Output is correct
5 Correct 169 ms 9964 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 14352 KB Output is correct
2 Correct 303 ms 14340 KB Output is correct
3 Correct 162 ms 14412 KB Output is correct
4 Correct 165 ms 14320 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 219 ms 16004 KB Output is correct
2 Correct 221 ms 16000 KB Output is correct
3 Correct 242 ms 16004 KB Output is correct
4 Correct 208 ms 15792 KB Output is correct
5 Correct 206 ms 11384 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 16004 KB Output is correct
2 Correct 275 ms 16084 KB Output is correct
3 Correct 217 ms 15964 KB Output is correct
4 Correct 198 ms 15948 KB Output is correct
5 Correct 176 ms 11456 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 17576 KB Output is correct
2 Correct 312 ms 17616 KB Output is correct
3 Correct 255 ms 17524 KB Output is correct
4 Correct 247 ms 17452 KB Output is correct
5 Correct 200 ms 12876 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 17444 KB Output is correct
2 Correct 306 ms 17468 KB Output is correct
3 Correct 269 ms 17604 KB Output is correct
4 Correct 231 ms 17452 KB Output is correct
5 Correct 203 ms 12980 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 20628 KB Output is correct
2 Correct 321 ms 20628 KB Output is correct
3 Correct 379 ms 20568 KB Output is correct
4 Correct 261 ms 16104 KB Output is correct
5 Correct 330 ms 16072 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 16972 KB Output is correct
2 Correct 407 ms 20572 KB Output is correct
3 Correct 282 ms 20784 KB Output is correct
4 Correct 259 ms 16132 KB Output is correct
5 Correct 273 ms 16080 KB Output is correct