oj.uz

Submission #684601

# Submission time Handle Problem Language Result Execution time Memory
684601 2023-01-22T00:45:07 Z aaggupta07 Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 20812 KB 
// Source: https://usaco.guide/general/io

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

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

constexpr int MAX_C = 3 * 10e9;
constexpr int MAX_N = 10e6;
constexpr double tol = 0.00000001L;

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

int n, l;
pi towers[MAX_N];

bool doubleEq(double a, double b) {
	return abs(a - b) <= tol;
}

double calcDist(int i, double d) {
	return sqrt((d * d) - (towers[i].s * towers[i].s));
}

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

	double start = MAX_C, curEnd = -1 * MAX_C, bestEnd = -1 * MAX_C;
	for(int i = 0; i < n; ++i) {
		if(abs(towers[i].s) >= p || doubleEq(abs(towers[i].s), p)) continue;

		double dist = calcDist(towers[i].s, p), d1 = towers[i].f - dist, d2 = towers[i].f + dist;
		// if(p - 6.98 <= 0.1) cout << d1 << ' ' << d2 << endl;
		bestEnd = max(bestEnd, d2);

		if(d1 < curEnd || doubleEq(d1, curEnd) || i == 0) {
			start = min(start, d1);
			curEnd = max(curEnd, bestEnd);
		}
	}

	// if(p - 6.98 <= 0.1) {
	// 	cout << "------------------" << endl;
	// 	cout << start << ' ' << curEnd << '\n';
	// 	// for(int i = 0; i < n; ++i) cout << intervals[i].f << ' ' << intervals[i].s << endl;
	// 	cout << "------------------" << endl;
	// }

	if((start < 0 || doubleEq(start, 0)) && (curEnd >= l || doubleEq(curEnd, l))) return true;
	return false;
}

signed main() {
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> towers[i].f >> towers[i].s;
	
	double ans = MAX_C, b = MAX_C/2;
	for(int i = 0; i < 50; ++i) {
		if((ans - b) >= 0 && check(ans - b)) ans -= b;
		b /= 2;
	}
	cout.precision(4);
	cout << fixed << ans << '\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 1584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 1640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 1796 KB Output is correct
2 Incorrect 92 ms 1648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 1980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 8244 KB Output is correct
2 Incorrect 895 ms 8396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 8352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 9896 KB Output is correct
2 Execution timed out 1031 ms 14152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 9788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 11260 KB Output is correct
2 Execution timed out 1016 ms 15620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 11344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 12944 KB Output is correct
2 Execution timed out 1034 ms 17260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 12876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 16152 KB Output is correct
2 Execution timed out 1042 ms 20812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 15972 KB Time limit exceeded
2 Halted 0 ms 0 KB -