Submission #481867

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
481867	2021-10-22T04:20:23 Z	wwdd	Mobile (BOI12_mobile)	C++14	100 / 100	445 ms	16948 KB

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<45;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.0 / 4.0

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

Subtask #2
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 #3
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	2504 KB	Output is correct
2	Correct	27 ms	2456 KB	Output is correct
3	Correct	14 ms	1484 KB	Output is correct
4	Correct	18 ms	2504 KB	Output is correct
5	Correct	9 ms	1484 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2504 KB	Output is correct
2	Correct	17 ms	2504 KB	Output is correct
3	Correct	18 ms	2408 KB	Output is correct
4	Correct	19 ms	2504 KB	Output is correct
5	Correct	26 ms	2504 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	2504 KB	Output is correct
2	Correct	26 ms	2476 KB	Output is correct
3	Correct	21 ms	2416 KB	Output is correct
4	Correct	26 ms	2460 KB	Output is correct
5	Correct	18 ms	2512 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	2516 KB	Output is correct
2	Correct	35 ms	2436 KB	Output is correct
3	Correct	26 ms	2504 KB	Output is correct
4	Correct	27 ms	2476 KB	Output is correct
5	Correct	21 ms	2504 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	2404 KB	Output is correct
2	Correct	35 ms	2488 KB	Output is correct
3	Correct	27 ms	2504 KB	Output is correct
4	Correct	27 ms	2472 KB	Output is correct
5	Correct	21 ms	2504 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	8628 KB	Output is correct
2	Correct	183 ms	8612 KB	Output is correct
3	Correct	136 ms	8584 KB	Output is correct
4	Correct	125 ms	8644 KB	Output is correct
5	Correct	108 ms	8624 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	8644 KB	Output is correct
2	Correct	233 ms	8636 KB	Output is correct
3	Correct	126 ms	8648 KB	Output is correct
4	Correct	130 ms	8608 KB	Output is correct
5	Correct	114 ms	8616 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	268 ms	16852 KB	Output is correct
2	Correct	216 ms	16804 KB	Output is correct
3	Correct	181 ms	16752 KB	Output is correct
4	Correct	161 ms	16816 KB	Output is correct
5	Correct	132 ms	16804 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	261 ms	16868 KB	Output is correct
2	Correct	273 ms	16936 KB	Output is correct
3	Correct	161 ms	16856 KB	Output is correct
4	Correct	159 ms	16848 KB	Output is correct
5	Correct	138 ms	16784 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	304 ms	16784 KB	Output is correct
2	Correct	241 ms	16740 KB	Output is correct
3	Correct	231 ms	16892 KB	Output is correct
4	Correct	185 ms	16836 KB	Output is correct
5	Correct	149 ms	16840 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	286 ms	16860 KB	Output is correct
2	Correct	301 ms	16768 KB	Output is correct
3	Correct	187 ms	16776 KB	Output is correct
4	Correct	189 ms	16860 KB	Output is correct
5	Correct	157 ms	16784 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	16804 KB	Output is correct
2	Correct	301 ms	16804 KB	Output is correct
3	Correct	219 ms	16804 KB	Output is correct
4	Correct	212 ms	16804 KB	Output is correct
5	Correct	178 ms	16800 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	330 ms	16764 KB	Output is correct
2	Correct	333 ms	16756 KB	Output is correct
3	Correct	201 ms	16824 KB	Output is correct
4	Correct	214 ms	16880 KB	Output is correct
5	Correct	181 ms	16836 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	445 ms	16800 KB	Output is correct
2	Correct	287 ms	16804 KB	Output is correct
3	Correct	336 ms	16868 KB	Output is correct
4	Correct	261 ms	16800 KB	Output is correct
5	Correct	217 ms	16760 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	445 ms	16948 KB	Output is correct
2	Correct	409 ms	16804 KB	Output is correct
3	Correct	276 ms	16840 KB	Output is correct
4	Correct	259 ms	16856 KB	Output is correct
5	Correct	226 ms	16836 KB	Output is correct

Submission #481867

Compilation message