oj.uz

Submission #460663

# Submission time Handle Problem Language Result Execution time Memory
460663 2021-08-09T08:19:03 Z shivensinha4 Mobile (BOI12_mobile) C++17
100 / 100
 709 ms 50936 KB 
#include <bits/stdc++.h>
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long double ll;
typedef vector<int> vi;
typedef array<ll, 2> ii;
//#define endl '\n'

int readInt () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}

const ll K = 1e5;

int main() {
#ifdef mlocal
	freopen("test_input.txt", "r", stdin);
//	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	ll n = readInt(), len = readInt();
//	cin >> n >> len;
	len *= K;
	vector<ii> pts(n);
	for_(i, 0, n) {
		for_(j, 0, 2) {
			pts[i][j] = readInt();
//			cin >> pts[i][j];
			pts[i][j] *= K;
		}
	}
	
	long long l = 0, r = 1e15, ans = l;
	ll pmid;
	while (l < r) {
		ll mid = (l+r)/2;
		assert(pmid != mid);
		pmid = mid;
		bool hole = false;
		ll cr = 0;
		for_(i, 0, n) if (mid*mid >= pts[i][1]*pts[i][1]) {
			ll sq = floor(sqrt(mid*mid - pts[i][1]*pts[i][1]));
			if (pts[i][0]-sq <= cr) {
				cr = max(cr, pts[i][0]+sq);
			}
		}
		
		if (hole or cr < len) {
			ans = mid;
			l = mid+1;
		} else r = mid;
	}
	
	cout << fixed << setprecision(10) << ans/K << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2660 KB Output is correct
2 Correct 53 ms 2704 KB Output is correct
3 Correct 38 ms 1868 KB Output is correct
4 Correct 37 ms 2688 KB Output is correct
5 Correct 23 ms 1888 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2764 KB Output is correct
2 Correct 34 ms 2508 KB Output is correct
3 Correct 35 ms 2856 KB Output is correct
4 Correct 31 ms 2804 KB Output is correct
5 Correct 34 ms 3020 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3056 KB Output is correct
2 Correct 57 ms 2892 KB Output is correct
3 Correct 51 ms 2892 KB Output is correct
4 Correct 34 ms 3404 KB Output is correct
5 Correct 38 ms 3020 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3436 KB Output is correct
2 Correct 67 ms 3440 KB Output is correct
3 Correct 61 ms 3404 KB Output is correct
4 Correct 36 ms 5356 KB Output is correct
5 Correct 44 ms 4700 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3404 KB Output is correct
2 Correct 67 ms 3404 KB Output is correct
3 Correct 64 ms 3404 KB Output is correct
4 Correct 35 ms 3404 KB Output is correct
5 Correct 45 ms 4684 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 15960 KB Output is correct
2 Correct 347 ms 23668 KB Output is correct
3 Correct 351 ms 23196 KB Output is correct
4 Correct 179 ms 25512 KB Output is correct
5 Correct 214 ms 22780 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 15964 KB Output is correct
2 Correct 346 ms 22492 KB Output is correct
3 Correct 314 ms 21708 KB Output is correct
4 Correct 180 ms 25284 KB Output is correct
5 Correct 207 ms 23252 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 19092 KB Output is correct
2 Correct 409 ms 28364 KB Output is correct
3 Correct 420 ms 27772 KB Output is correct
4 Correct 231 ms 30980 KB Output is correct
5 Correct 269 ms 27068 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 19092 KB Output is correct
2 Correct 414 ms 27016 KB Output is correct
3 Correct 365 ms 26000 KB Output is correct
4 Correct 220 ms 30916 KB Output is correct
5 Correct 274 ms 27852 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 22224 KB Output is correct
2 Correct 478 ms 33056 KB Output is correct
3 Correct 481 ms 32372 KB Output is correct
4 Correct 250 ms 35652 KB Output is correct
5 Correct 301 ms 31244 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 22224 KB Output is correct
2 Correct 460 ms 31416 KB Output is correct
3 Correct 423 ms 30660 KB Output is correct
4 Correct 255 ms 35584 KB Output is correct
5 Correct 294 ms 32344 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 25324 KB Output is correct
2 Correct 573 ms 37748 KB Output is correct
3 Correct 551 ms 37040 KB Output is correct
4 Correct 285 ms 40984 KB Output is correct
5 Correct 332 ms 36496 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 25356 KB Output is correct
2 Correct 500 ms 35984 KB Output is correct
3 Correct 484 ms 34940 KB Output is correct
4 Correct 285 ms 40828 KB Output is correct
5 Correct 344 ms 36860 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 31620 KB Output is correct
2 Correct 698 ms 47132 KB Output is correct
3 Correct 689 ms 46156 KB Output is correct
4 Correct 372 ms 50796 KB Output is correct
5 Correct 438 ms 45176 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 31616 KB Output is correct
2 Correct 628 ms 44848 KB Output is correct
3 Correct 592 ms 43892 KB Output is correct
4 Correct 407 ms 50936 KB Output is correct
5 Correct 415 ms 46280 KB Output is correct