Submission #965072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965072	2024-04-18T05:01:25 Z	pcc	Mobile (BOI12_mobile)	C++17	8 / 100	876 ms	56280 KB

mobile

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ld double
#define pld pair<ld,ld>

const int mxn = 1e6+10;
ll N,L;
vector<pll> arr;

inline bool check(ld r){
	vector<pld> v;
	for(int i = 0;i<N;i++){
		if(r<arr[i].sc)continue;
		v.push_back(pld(arr[i].fs-sqrt(r*r-arr[i].sc*arr[i].sc),arr[i].fs+sqrt(r*r-arr[i].sc*arr[i].sc)));
		if(v.back().fs<0&&v.back().sc>L)return true;
	}
	//sort(v.begin(),v.end());
	ld pre = 0;
	for(auto &i:v){
		if(pre>L)return true;
		if(i.fs<=pre)pre = max(pre,i.sc);
	}
	return pre>L;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ld l = 0,r = 1e9*sqrt(2);
	cin>>N>>L;
	for(int i = 0;i<N;i++){
		pll tmp;
		cin>>tmp.fs>>tmp.sc;
		if(i&&tmp.fs == arr.back().fs)arr.back().sc = min(arr.back().sc,tmp.sc);
		else arr.push_back(pll(tmp.fs,abs(tmp.sc)));
	}
	for(int i = 0;r-l>0.001;i++){
		ld mid = (l+r)/2;
		if(check(mid))r = mid;
		else l = mid;
	}
	cout<<fixed<<setprecision(10)<<l<<'\n';
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	708 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
4.0 / 4.0

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

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	724 KB	Output is correct
2	Correct	3 ms	780 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	2 ms	744 KB	Output is correct
5	Incorrect	2 ms	468 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	5576 KB	Output is correct
2	Runtime error	14 ms	5720 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	1956 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	6052 KB	Output is correct
2	Runtime error	19 ms	5596 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	20 ms	5864 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	7436 KB	Output is correct
2	Runtime error	18 ms	5668 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	28664 KB	Output is correct
2	Runtime error	66 ms	9180 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	75 ms	9740 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	539 ms	43408 KB	Output is correct
2	Runtime error	80 ms	10472 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	90 ms	10912 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	615 ms	46744 KB	Output is correct
2	Runtime error	102 ms	12060 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	98 ms	12444 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	720 ms	50572 KB	Output is correct
2	Runtime error	121 ms	12424 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	111 ms	13328 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	876 ms	56280 KB	Output is correct
2	Runtime error	137 ms	15144 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	144 ms	15896 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Submission #965072

Compilation message