Submission #445975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445975	2021-07-20T10:12:21 Z	Qw3rTy	Mobile (BOI12_mobile)	C++11	80 / 100	732 ms	34708 KB

mobile

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
#define db double
#define delta 1e-6
#define pi pair<int,int>
#define pb pair<db,db>
#define fi first
#define se second
using namespace std;

const int maxN = 1e6+5;

int N,L;
pi tower[maxN];
pb inter[maxN]; //intersections

bool cmp(pb a, pb b){
	if(abs(a.fi - b.fi) < delta)return a.se < b.se;
	return a.fi < b.fi;
}

bool works(db r){
	//Reset inter array
	for(int i = 1; i <= N; ++i){
		inter[i].fi = 0;
		inter[i].se = -1;
	}
	for(int i = 1; i <= N; ++i) {
		//Can't reach any point on the highway
		if (abs(r) < abs(tower[i].se))continue;
		inter[i].fi = tower[i].fi - sqrt(r*r - tower[i].se*tower[i].se);
		inter[i].se = tower[i].fi + sqrt(r*r - tower[i].se*tower[i].se);
		inter[i].fi = (inter[i].fi < 0)?0:inter[i].fi;
		inter[i].se = (inter[i].se > L)?L:inter[i].se;
	}
	if(N <= 1e5)sort(inter+1,inter+N+1,cmp);
	db b = delta;
	if(abs(inter[1].fi) > 0)return false;
	for(int i = 1; i <= N; ++i){
		//Invalid intersections
		if(inter[i].fi > inter[i].se)continue;
		//Merge intervals
		if(inter[i].fi <= b){
			b = (inter[i].se > b)?inter[i].se:b;
		}
	}
	if(abs(b-L) < delta)return true;
	return false;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("../test.in","r",stdin);
	cin >> N >> L;
	for(int i = 1; i <= N; ++i)cin >> tower[i].fi >> tower[i].se;
	db low = 1; db high = L;
	while(abs(high-low) > delta){
		db mid = (low+high)/2;
		if(works(mid))high = mid;
		else low = mid + delta;
	}
	cout << setprecision(12) << low  << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	460 KB	Output is correct
2	Correct	13 ms	536 KB	Output is correct
3	Correct	16 ms	524 KB	Output is correct
4	Correct	10 ms	460 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	460 KB	Output is correct
2	Correct	13 ms	560 KB	Output is correct
3	Correct	13 ms	528 KB	Output is correct
4	Correct	11 ms	564 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	544 KB	Output is correct
2	Correct	13 ms	552 KB	Output is correct
3	Correct	13 ms	528 KB	Output is correct
4	Correct	11 ms	460 KB	Output is correct
5	Correct	8 ms	460 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	3012 KB	Output is correct
2	Correct	298 ms	2944 KB	Output is correct
3	Correct	205 ms	2276 KB	Output is correct
4	Correct	185 ms	3028 KB	Output is correct
5	Correct	80 ms	2176 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	3140 KB	Output is correct
2	Correct	149 ms	2808 KB	Output is correct
3	Correct	180 ms	3140 KB	Output is correct
4	Correct	198 ms	3076 KB	Output is correct
5	Correct	228 ms	3312 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	251 ms	3276 KB	Output is correct
2	Correct	342 ms	3180 KB	Output is correct
3	Correct	370 ms	3268 KB	Output is correct
4	Correct	281 ms	3708 KB	Output is correct
5	Correct	183 ms	3384 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	388 ms	3736 KB	Output is correct
2	Correct	465 ms	3780 KB	Output is correct
3	Correct	415 ms	3780 KB	Output is correct
4	Correct	281 ms	3848 KB	Output is correct
5	Correct	274 ms	3732 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	359 ms	3728 KB	Output is correct
2	Correct	445 ms	3728 KB	Output is correct
3	Correct	475 ms	3780 KB	Output is correct
4	Correct	316 ms	3732 KB	Output is correct
5	Correct	213 ms	3728 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	354 ms	16640 KB	Output is correct
2	Correct	330 ms	18084 KB	Output is correct
3	Correct	316 ms	19156 KB	Output is correct
4	Correct	285 ms	19160 KB	Output is correct
5	Correct	245 ms	19140 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	352 ms	16672 KB	Output is correct
2	Correct	403 ms	19224 KB	Output is correct
3	Correct	271 ms	19296 KB	Output is correct
4	Correct	283 ms	19160 KB	Output is correct
5	Correct	244 ms	19228 KB	Output is correct

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	417 ms	19880 KB	Output is correct
2	Incorrect	407 ms	21152 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	19884 KB	Output is correct
2	Correct	486 ms	22356 KB	Output is correct
3	Correct	330 ms	22256 KB	Output is correct
4	Correct	324 ms	22124 KB	Output is correct
5	Correct	285 ms	22260 KB	Output is correct

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	23012 KB	Output is correct
2	Incorrect	476 ms	24152 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	486 ms	23008 KB	Output is correct
2	Correct	515 ms	25420 KB	Output is correct
3	Correct	410 ms	25420 KB	Output is correct
4	Correct	393 ms	25288 KB	Output is correct
5	Correct	341 ms	25356 KB	Output is correct

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	533 ms	26140 KB	Output is correct
2	Incorrect	539 ms	27288 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	563 ms	26152 KB	Output is correct
2	Correct	581 ms	28424 KB	Output is correct
3	Correct	459 ms	28556 KB	Output is correct
4	Correct	451 ms	28484 KB	Output is correct
5	Correct	406 ms	28424 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	723 ms	32380 KB	Output is correct
2	Incorrect	678 ms	33628 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	703 ms	32320 KB	Output is correct
2	Correct	732 ms	34664 KB	Output is correct
3	Correct	564 ms	34708 KB	Output is correct
4	Correct	581 ms	31888 KB	Output is correct
5	Correct	505 ms	34572 KB	Output is correct

Submission #445975

Compilation message