oj.uz

Submission #735130

# Submission time Handle Problem Language Result Execution time Memory
735130 2023-05-03T15:11:10 Z ace_in_the_hole Mobile (BOI12_mobile) C++17
100 / 100
 314 ms 26700 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long Int;
typedef double Real;
const Real EPS = 1e-6;
bool leq(Real x, Real y) { return x-EPS <= y; }

const int N = 1e6 + 50;
int n,L, x[N];
Int y[N];

bool check(Real dis) {
	Real rightmost = 0;
	Real d_squared = dis * dis;
	for (int i = 1; i <= n; i++) {
		if (leq(d_squared, y[i])) continue;
		Real lef = x[i] - sqrt(d_squared - y[i]);
		Real rig = 2*x[i] - lef;
		if (leq(lef, rightmost)) {
			rightmost = max(rightmost, rig);
			if (leq(L,rightmost)) return true;
		}
	}
	return false;
}

void solve() 
{
	cin >> n >> L;
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	//preprocessing
	Real max_dist = L;
	for (int i = 1; i <= n; i++) {
		y[i] *= y[i];
		int x_dis = max(abs(x[i]), abs(L - x[i]));
		Real cur_dist = sqrt(y[i] + 1ll * x_dis * x_dis);
		max_dist = max(max_dist, cur_dist);
	}
	const Real DEL = 1e-3;
	Real ans = 0;
	for (Real low = 0, high = max_dist + 100; high - low >= DEL; ) {
		Real mid = (low + high) / 2;
		if (check(mid)) high = mid;
		else ans = low = mid;
	}
	cout << fixed << setprecision(15) << ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	#define task "WF"
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:58:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 324 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 2 ms 344 KB Output is correct
3 Correct 1 ms 344 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 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 464 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 2 ms 340 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 468 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 20 ms 1148 KB Output is correct
2 Correct 17 ms 2296 KB Output is correct
3 Correct 11 ms 1480 KB Output is correct
4 Correct 20 ms 2388 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1164 KB Output is correct
2 Correct 15 ms 1976 KB Output is correct
3 Correct 20 ms 2216 KB Output is correct
4 Correct 20 ms 2448 KB Output is correct
5 Correct 23 ms 2776 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1372 KB Output is correct
2 Correct 18 ms 1236 KB Output is correct
3 Correct 17 ms 2272 KB Output is correct
4 Correct 29 ms 3332 KB Output is correct
5 Correct 18 ms 2260 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1448 KB Output is correct
2 Correct 21 ms 1508 KB Output is correct
3 Correct 19 ms 2508 KB Output is correct
4 Correct 28 ms 3444 KB Output is correct
5 Correct 23 ms 2660 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1460 KB Output is correct
2 Correct 24 ms 2900 KB Output is correct
3 Correct 21 ms 2524 KB Output is correct
4 Correct 28 ms 3404 KB Output is correct
5 Correct 22 ms 2668 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 6188 KB Output is correct
2 Correct 115 ms 6116 KB Output is correct
3 Correct 113 ms 8520 KB Output is correct
4 Correct 130 ms 8448 KB Output is correct
5 Correct 118 ms 8460 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 6220 KB Output is correct
2 Correct 208 ms 6300 KB Output is correct
3 Correct 116 ms 8428 KB Output is correct
4 Correct 132 ms 8476 KB Output is correct
5 Correct 121 ms 8372 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 7368 KB Output is correct
2 Correct 147 ms 7408 KB Output is correct
3 Correct 126 ms 7416 KB Output is correct
4 Correct 179 ms 10040 KB Output is correct
5 Correct 144 ms 9956 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 7748 KB Output is correct
2 Correct 200 ms 7752 KB Output is correct
3 Correct 132 ms 9876 KB Output is correct
4 Correct 156 ms 9848 KB Output is correct
5 Correct 131 ms 9824 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8928 KB Output is correct
2 Correct 188 ms 8920 KB Output is correct
3 Correct 147 ms 8924 KB Output is correct
4 Correct 201 ms 11040 KB Output is correct
5 Correct 160 ms 11100 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 8928 KB Output is correct
2 Correct 243 ms 8836 KB Output is correct
3 Correct 164 ms 10952 KB Output is correct
4 Correct 211 ms 10844 KB Output is correct
5 Correct 193 ms 10876 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 10088 KB Output is correct
2 Correct 220 ms 10088 KB Output is correct
3 Correct 197 ms 12024 KB Output is correct
4 Correct 242 ms 12008 KB Output is correct
5 Correct 204 ms 11860 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 10092 KB Output is correct
2 Correct 265 ms 10084 KB Output is correct
3 Correct 169 ms 11700 KB Output is correct
4 Correct 240 ms 11748 KB Output is correct
5 Correct 186 ms 11604 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 12332 KB Output is correct
2 Correct 260 ms 12400 KB Output is correct
3 Correct 231 ms 12428 KB Output is correct
4 Correct 291 ms 12108 KB Output is correct
5 Correct 267 ms 25608 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 11972 KB Output is correct
2 Correct 314 ms 12432 KB Output is correct
3 Correct 233 ms 13632 KB Output is correct
4 Correct 307 ms 11980 KB Output is correct
5 Correct 276 ms 26700 KB Output is correct