Submission #965070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965070	2024-04-18T05:00:32 Z	pcc	Mobile (BOI12_mobile)	C++17	8 / 100	936 ms	57064 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(pre<i.fs)return false;
		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	348 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	2 ms	612 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	720 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	540 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	2008 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	70 ms	6004 KB	Output is correct
2	Runtime error	15 ms	5716 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	17 ms	5672 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	102 ms	7216 KB	Output is correct
2	Runtime error	19 ms	5628 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	436 ms	29156 KB	Output is correct
2	Runtime error	66 ms	9236 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	9712 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	523 ms	40992 KB	Output is correct
2	Runtime error	96 ms	10576 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	91 ms	11164 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	667 ms	45000 KB	Output is correct
2	Runtime error	129 ms	12028 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	108 ms	12776 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	757 ms	49072 KB	Output is correct
2	Runtime error	116 ms	13696 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	125 ms	14364 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	936 ms	57064 KB	Output is correct
2	Runtime error	141 ms	16572 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	151 ms	17536 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Submission #965070

Compilation message