oj.uz

Submission #554957

# Submission time Handle Problem Language Result Execution time Memory
554957 2022-04-29T18:03:37 Z victor_gao Mobile (BOI12_mobile) C++17
100 / 100
 660 ms 35456 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=max(dr,r); 
	}
	if (r>=(double)L){
		return 1;
	}
	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;
	}
	sort(arr+1,arr+1+n);
	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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
4.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 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 4 ms 468 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 396 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2092 KB Output is correct
2 Correct 47 ms 2564 KB Output is correct
3 Correct 28 ms 1752 KB Output is correct
4 Correct 39 ms 2624 KB Output is correct
5 Correct 23 ms 1492 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2028 KB Output is correct
2 Correct 36 ms 2232 KB Output is correct
3 Correct 41 ms 2620 KB Output is correct
4 Correct 39 ms 2720 KB Output is correct
5 Correct 41 ms 3144 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2036 KB Output is correct
2 Correct 50 ms 2036 KB Output is correct
3 Correct 49 ms 2516 KB Output is correct
4 Correct 50 ms 3808 KB Output is correct
5 Correct 46 ms 2628 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2396 KB Output is correct
2 Correct 63 ms 3292 KB Output is correct
3 Correct 54 ms 2808 KB Output is correct
4 Correct 56 ms 3836 KB Output is correct
5 Correct 53 ms 3144 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2348 KB Output is correct
2 Correct 74 ms 2396 KB Output is correct
3 Correct 56 ms 2920 KB Output is correct
4 Correct 53 ms 3824 KB Output is correct
5 Correct 52 ms 3168 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 8652 KB Output is correct
2 Correct 294 ms 8724 KB Output is correct
3 Correct 314 ms 10028 KB Output is correct
4 Correct 268 ms 9420 KB Output is correct
5 Correct 309 ms 14944 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 8656 KB Output is correct
2 Correct 397 ms 10136 KB Output is correct
3 Correct 270 ms 13900 KB Output is correct
4 Correct 274 ms 17372 KB Output is correct
5 Correct 269 ms 15504 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 10224 KB Output is correct
2 Correct 380 ms 10016 KB Output is correct
3 Correct 430 ms 13036 KB Output is correct
4 Correct 346 ms 12192 KB Output is correct
5 Correct 330 ms 17712 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 10316 KB Output is correct
2 Correct 482 ms 13248 KB Output is correct
3 Correct 342 ms 16548 KB Output is correct
4 Correct 343 ms 21452 KB Output is correct
5 Correct 356 ms 18448 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 12076 KB Output is correct
2 Correct 480 ms 11888 KB Output is correct
3 Correct 439 ms 13896 KB Output is correct
4 Correct 406 ms 13800 KB Output is correct
5 Correct 373 ms 20204 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 11884 KB Output is correct
2 Correct 559 ms 14288 KB Output is correct
3 Correct 427 ms 19668 KB Output is correct
4 Correct 391 ms 24672 KB Output is correct
5 Correct 405 ms 21408 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 13880 KB Output is correct
2 Correct 503 ms 13692 KB Output is correct
3 Correct 530 ms 15616 KB Output is correct
4 Correct 427 ms 15788 KB Output is correct
5 Correct 440 ms 24012 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 13736 KB Output is correct
2 Correct 531 ms 15760 KB Output is correct
3 Correct 417 ms 22376 KB Output is correct
4 Correct 397 ms 28236 KB Output is correct
5 Correct 386 ms 24392 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 17144 KB Output is correct
2 Correct 562 ms 16984 KB Output is correct
3 Correct 572 ms 18920 KB Output is correct
4 Correct 486 ms 17012 KB Output is correct
5 Correct 523 ms 29560 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 16020 KB Output is correct
2 Correct 660 ms 18896 KB Output is correct
3 Correct 531 ms 28380 KB Output is correct
4 Correct 496 ms 35456 KB Output is correct
5 Correct 514 ms 30728 KB Output is correct