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
#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;
}
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 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 -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 5864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 9740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 10912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 98 ms 12444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 13328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 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 -
# Verdict Execution time Memory Grader output
1 Runtime error 144 ms 15896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -