oj.uz

Submission #554954

# Submission time Handle Problem Language Result Execution time Memory
554954 2022-04-29T18:01:19 Z victor_gao Mobile (BOI12_mobile) C++17
0 / 100
 979 ms 97760 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define double long double
#define pii pair<int,int>
#define x first
#define y second
#define N 1000015
#define eps 1e-8
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,L;
pii arr[N];
map<int,int>mp;
bool check(double val){
	//cout<<sqrt(val)<<" -> \n";
	double r=0;
	for (int i=1;i<=n;i++){
		if (val*val-arr[i].y*arr[i].y<=eps) continue;
		double dl=(double)arr[i].x-sqrt(val*val-arr[i].y*arr[i].y);
		double dr=(double)arr[i].x+sqrt(val*val-arr[i].y*arr[i].y);
		if (dl<=r) r=dr; 
	}
	if (r>=L){
	//	cout<<"OK\n";
		return 1;
	}
//	cout<<"NO\n";
	return 0;
}
signed main(){
	fast
//	freopen("loan.in","r",stdin);
//	freopen("loan.out","w",stdout);
	cout<<fixed<<setprecision(5);
	cin>>n>>L;
	for (int i=1;i<=n;i++){
		cin>>arr[i].x>>arr[i].y;
		if (!mp[arr[i].x]) mp[arr[i].x]=arr[i].y;
		else mp[arr[i].x]=min(arr[i].y,mp[arr[i].x]);
	}
	n=0;
	for (auto i:mp)	arr[++n]=i;
	double l=0,r=4e18;
	while (r-l>0.00001){
		double mid=(l+r)/2.0;
	//	cout<<l<<" ~ "<<r<<'\n';
		if (check(mid)) r=mid;
		else l=mid;
	}
	cout<<(double)(l)<<'\n';
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7852 KB Output is correct
2 Correct 55 ms 5296 KB Output is correct
3 Correct 62 ms 7120 KB Output is correct
4 Incorrect 77 ms 10028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5068 KB Output is correct
2 Correct 67 ms 5992 KB Output is correct
3 Correct 41 ms 3820 KB Output is correct
4 Incorrect 77 ms 10112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8628 KB Output is correct
2 Correct 74 ms 5036 KB Output is correct
3 Correct 42 ms 3792 KB Output is correct
4 Incorrect 75 ms 10060 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 40064 KB Output is correct
2 Correct 178 ms 9224 KB Output is correct
3 Correct 183 ms 15916 KB Output is correct
4 Incorrect 394 ms 49008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 9076 KB Output is correct
2 Incorrect 495 ms 45684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 47808 KB Output is correct
2 Correct 212 ms 10560 KB Output is correct
3 Correct 208 ms 18748 KB Output is correct
4 Incorrect 480 ms 59280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 10640 KB Output is correct
2 Incorrect 613 ms 54696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 55624 KB Output is correct
2 Correct 226 ms 12176 KB Output is correct
3 Correct 236 ms 21808 KB Output is correct
4 Incorrect 576 ms 68632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 12148 KB Output is correct
2 Incorrect 706 ms 63788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 63548 KB Output is correct
2 Correct 269 ms 13752 KB Output is correct
3 Correct 256 ms 24724 KB Output is correct
4 Incorrect 655 ms 78504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 13584 KB Output is correct
2 Incorrect 808 ms 72820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 79244 KB Output is correct
2 Correct 315 ms 25648 KB Output is correct
3 Correct 309 ms 30788 KB Output is correct
4 Incorrect 858 ms 97760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 16344 KB Output is correct
2 Incorrect 979 ms 90572 KB Output isn't correct
3 Halted 0 ms 0 KB -