oj.uz

Submission #1079735

# Submission time Handle Problem Language Result Execution time Memory
1079735 2024-08-28T23:25:10 Z EmmaXII Mobile (BOI12_mobile) C++17
65 / 100
 282 ms 16124 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

#define all(x) x.begin(), x.end()


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N;
	ll L;
	cin >> N >> L;

	vector<ll> X(N);
	vector<ll> Y(N);
	for (int i=0;i<N;i++) cin >> X[i] >> Y[i];

	auto get_hw = [&](double y, double r) {
		if (abs(y) > r - 1e-6) return -1.0;
		return sqrt((r-y) * (r+y));
	};

	auto can_do = [&](double R) {
		double progress = 0.;
		for (int i=0;i<N;i++) {
			double hw = get_hw((double)Y[i], R);
			if (hw < 0) continue;

			double l = (double)X[i] - hw;
			double r = (double)X[i] + hw;
			if (l <= progress + 1e-6) progress = max(progress, r);
			if (progress >= (double)L) return true;
		}

		return false;
	};

	double lo = 1;
	double hi = 2e9;

	while (hi - lo > 1e-4) {
		double mid = (lo + hi) / 2;
		if (can_do(mid)) hi = mid;
		else lo = mid;
	}
	cout << setprecision(10);
	cout << (lo + hi)/2 << endl;

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1628 KB Output is correct
2 Correct 15 ms 1624 KB Output is correct
3 Correct 8 ms 1116 KB Output is correct
4 Correct 13 ms 1628 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1628 KB Output is correct
2 Correct 11 ms 1372 KB Output is correct
3 Correct 15 ms 1736 KB Output is correct
4 Correct 15 ms 1628 KB Output is correct
5 Correct 16 ms 1828 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1628 KB Output is correct
2 Correct 14 ms 1756 KB Output is correct
3 Correct 13 ms 1628 KB Output is correct
4 Correct 19 ms 2032 KB Output is correct
5 Correct 17 ms 1624 KB Output is correct

Subtask #10
0 / 5.0

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

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1880 KB Output is correct
2 Correct 18 ms 1884 KB Output is correct
3 Correct 14 ms 1880 KB Output is correct
4 Correct 21 ms 2040 KB Output is correct
5 Correct 19 ms 2040 KB Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 8284 KB Output is correct
2 Correct 159 ms 8280 KB Output is correct
3 Correct 80 ms 8284 KB Output is correct
4 Correct 98 ms 8284 KB Output is correct
5 Correct 80 ms 8284 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 9820 KB Output is correct
2 Incorrect 104 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 11352 KB Output is correct
2 Incorrect 139 ms 11408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 11356 KB Output is correct
2 Correct 212 ms 11408 KB Output is correct
3 Correct 109 ms 11404 KB Output is correct
4 Correct 134 ms 11856 KB Output is correct
5 Correct 113 ms 11352 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 12892 KB Output is correct
2 Incorrect 135 ms 12972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 12888 KB Output is correct
2 Correct 227 ms 12972 KB Output is correct
3 Correct 124 ms 12892 KB Output is correct
4 Correct 159 ms 12988 KB Output is correct
5 Correct 128 ms 12888 KB Output is correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 15960 KB Output is correct
2 Incorrect 174 ms 15964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 16108 KB Output is correct
2 Correct 282 ms 16108 KB Output is correct
3 Correct 148 ms 16124 KB Output is correct
4 Correct 196 ms 15964 KB Output is correct
5 Correct 158 ms 15960 KB Output is correct