Submission #481866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
481866	2021-10-22T04:18:10 Z	wwdd	Mobile (BOI12_mobile)	C++14	100 / 100	893 ms	35352 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<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.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	2504 KB	Output is correct
2	Correct	57 ms	2504 KB	Output is correct
3	Correct	23 ms	1484 KB	Output is correct
4	Correct	24 ms	2468 KB	Output is correct
5	Correct	12 ms	1484 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	2428 KB	Output is correct
2	Correct	29 ms	2512 KB	Output is correct
3	Correct	23 ms	2412 KB	Output is correct
4	Correct	25 ms	2396 KB	Output is correct
5	Correct	29 ms	2504 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	2556 KB	Output is correct
2	Correct	35 ms	2504 KB	Output is correct
3	Correct	45 ms	2504 KB	Output is correct
4	Correct	42 ms	2504 KB	Output is correct
5	Correct	31 ms	2520 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	2432 KB	Output is correct
2	Correct	39 ms	2504 KB	Output is correct
3	Correct	40 ms	2504 KB	Output is correct
4	Correct	36 ms	2420 KB	Output is correct
5	Correct	30 ms	2504 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	2484 KB	Output is correct
2	Correct	39 ms	2504 KB	Output is correct
3	Correct	44 ms	2424 KB	Output is correct
4	Correct	33 ms	2404 KB	Output is correct
5	Correct	29 ms	2504 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	449 ms	8628 KB	Output is correct
2	Correct	218 ms	8624 KB	Output is correct
3	Correct	180 ms	8624 KB	Output is correct
4	Correct	169 ms	8628 KB	Output is correct
5	Correct	145 ms	8572 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	8536 KB	Output is correct
2	Correct	523 ms	8704 KB	Output is correct
3	Correct	227 ms	8612 KB	Output is correct
4	Correct	176 ms	8596 KB	Output is correct
5	Correct	141 ms	8628 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	540 ms	16768 KB	Output is correct
2	Correct	293 ms	25172 KB	Output is correct
3	Correct	209 ms	24636 KB	Output is correct
4	Correct	231 ms	27428 KB	Output is correct
5	Correct	187 ms	24084 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	489 ms	16804 KB	Output is correct
2	Correct	608 ms	16892 KB	Output is correct
3	Correct	399 ms	16840 KB	Output is correct
4	Correct	209 ms	16744 KB	Output is correct
5	Correct	183 ms	16764 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	641 ms	16804 KB	Output is correct
2	Correct	508 ms	25088 KB	Output is correct
3	Correct	271 ms	24604 KB	Output is correct
4	Correct	233 ms	27256 KB	Output is correct
5	Correct	215 ms	23712 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	550 ms	16852 KB	Output is correct
2	Correct	630 ms	16804 KB	Output is correct
3	Correct	394 ms	16740 KB	Output is correct
4	Correct	228 ms	16844 KB	Output is correct
5	Correct	212 ms	16780 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	711 ms	16788 KB	Output is correct
2	Correct	628 ms	25424 KB	Output is correct
3	Correct	275 ms	24616 KB	Output is correct
4	Correct	286 ms	28620 KB	Output is correct
5	Correct	265 ms	24432 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	377 ms	16760 KB	Output is correct
2	Correct	688 ms	16816 KB	Output is correct
3	Correct	445 ms	23204 KB	Output is correct
4	Correct	274 ms	28440 KB	Output is correct
5	Correct	247 ms	24740 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	893 ms	16816 KB	Output is correct
2	Correct	663 ms	31732 KB	Output is correct
3	Correct	692 ms	30752 KB	Output is correct
4	Correct	345 ms	35320 KB	Output is correct
5	Correct	299 ms	29672 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	489 ms	16788 KB	Output is correct
2	Correct	784 ms	16804 KB	Output is correct
3	Correct	543 ms	28420 KB	Output is correct
4	Correct	360 ms	35352 KB	Output is correct
5	Correct	305 ms	30804 KB	Output is correct

Submission #481866

Compilation message