Submission #460663

#	Time	Username	Problem	Language	Result	Execution time	Memory
460663		shivensinha4	Mobile (BOI12_mobile)	C++17	100 / 100	709 ms	50936 KiB

mobile

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5