Submission #481866

#	Time	Username	Problem	Language	Result	Execution time	Memory
481866		wwdd	Mobile (BOI12_mobile)	C++14	100 / 100	893 ms	35352 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef pair<double,double> S;
S seg(pl a, double rad) {
	if(a.second > rad) {return {a.second,a.second};}
	double r = sqrt(rad*rad-a.second*a.second);
	return {a.first-r,a.first+r};
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,len;
	cin >> n >> len;
	vpl w;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		b = abs(b);
		w.emplace_back(a,b);
	}
	double st = 0;
	double ed = 4e9;
	double ls = ed;
	for(int iter=0;iter<100;iter++) {
		double m = (st+ed)/2;
		stack<S> sto;
		bool poss = false;
		for(int i=0;i<n;i++) {
			if(poss) {break;}
			if(m > w[i].second) {
				S se = seg(w[i],m);
				while(!sto.empty() && sto.top().second > se.first) {
					se.first = min(se.first,sto.top().first);
					se.second = max(se.second,sto.top().second);
					sto.pop();
				}
				if(se.first <= 0 && se.second >= len) {
					poss = true;
					break;
				}
				sto.push(se);
			}
		}
		if(poss) {
			ls = m;
			ed = m;
		} else {
			st = m;
		}
	}
	cout << fixed << setprecision(7) << ls << '\n';
}

• 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