oj.uz

Submission #554948

# Submission time Handle Problem Language Result Execution time Memory
554948 2022-04-29T17:32:51 Z victor_gao Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 32540 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 pii pair<int,int>
#define x first
#define y second
#define N 1000015
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];
bool check(double val){
	//cout<<sqrt(val)<<" -> \n";
	double l=0,r=-1;
	for (int i=1;i<=n;i++){
		if (val-arr[i].y*arr[i].y<=0) continue;
		double dl=(double)arr[i].x-sqrt(val-arr[i].y*arr[i].y);
		double dr=(double)arr[i].x+sqrt(val-arr[i].y*arr[i].y);
		if (l<r){
			if (dl-r>0.000001){
				l=dl;
			}
			else {
				r=max(r,dr);
			}
		}
		else {
			if (r-dl>0.000001){
				r=dr;
				l=dl;
			}
		}
//		cout<<l<<" "<<r<<'\n';
	}
	if (l<=r&&r>=L){
	//	cout<<"OK\n";
		return 1;
	}
//	cout<<"NO\n";
	return 0;
}
bool cmp(pii a,pii b){
	if (a.x!=b.x) return a.x<b.x;
	else return a.y>b.y;
} 
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;
	sort(arr+1,arr+1+n,cmp);
	double l=0,r=4e18;
	while (r-l>0.0001){
		double mid=(l+r)/2.0;
	//	cout<<l<<" ~ "<<r<<'\n';
		if (check(mid)) r=mid;
		else l=mid;
	}
	cout<<(long double)(sqrt(l))<<'\n';
}

Subtask #1
0 / 4.0

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

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Execution timed out 1078 ms 468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 344 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 488 KB Output is correct
2 Execution timed out 1075 ms 468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2348 KB Output is correct
2 Execution timed out 1083 ms 2724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3276 KB Output is correct
2 Execution timed out 1088 ms 3228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 12356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 16324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 14800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1038 ms 19632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 17284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 22776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 19708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 26056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 24664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 32540 KB Time limit exceeded
2 Halted 0 ms 0 KB -