oj.uz

Submission #965002

# Submission time Handle Problem Language Result Execution time Memory
965002 2024-04-18T02:50:25 Z pcc Mobile (BOI12_mobile) C++17
40 / 100
 1000 ms 79976 KB 
#include <bits/stdc++.h>
using namespace std;

#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 long double
#define pld pair<ld,ld>

const int mxn = 1e6+10;
ll N,L;
pair<ll,ll> arr[mxn];

inline bool check(ld r){
	vector<pld> v;
	for(int i = 0;i<N;i++){
		if(r<abs(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)));
	}
	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 = 2e9;
	cin>>N>>L;
	for(int i = 0;i<N;i++)cin>>arr[i].fs>>arr[i].sc;
	for(int i = 0;i<60;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 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 800 KB Output is correct
2 Correct 11 ms 744 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 9 ms 752 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1008 KB Output is correct
2 Correct 21 ms 1252 KB Output is correct
3 Correct 32 ms 1000 KB Output is correct
4 Correct 9 ms 1032 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1004 KB Output is correct
2 Correct 21 ms 1036 KB Output is correct
3 Correct 28 ms 1008 KB Output is correct
4 Correct 9 ms 1064 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1120 KB Output is correct
2 Correct 23 ms 1032 KB Output is correct
3 Correct 34 ms 1004 KB Output is correct
4 Correct 8 ms 1032 KB Output is correct
5 Correct 12 ms 1004 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 11440 KB Output is correct
2 Correct 584 ms 11520 KB Output is correct
3 Correct 368 ms 7120 KB Output is correct
4 Correct 133 ms 12040 KB Output is correct
5 Correct 139 ms 7288 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 10748 KB Output is correct
2 Correct 170 ms 11012 KB Output is correct
3 Correct 172 ms 10512 KB Output is correct
4 Correct 144 ms 11204 KB Output is correct
5 Correct 138 ms 11008 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 11092 KB Output is correct
2 Correct 624 ms 10604 KB Output is correct
3 Correct 880 ms 10424 KB Output is correct
4 Correct 96 ms 11716 KB Output is correct
5 Correct 244 ms 11724 KB Output is correct

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 12164 KB Output is correct
2 Correct 799 ms 11600 KB Output is correct
3 Execution timed out 1025 ms 10976 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 11480 KB Output is correct
2 Correct 799 ms 11628 KB Output is correct
3 Execution timed out 1060 ms 11444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 44496 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 1024 ms 47588 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 1016 ms 66212 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 1055 ms 68304 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 1049 ms 67836 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 1043 ms 71600 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 1004 ms 69920 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 1083 ms 76596 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 1026 ms 72816 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 1038 ms 79976 KB Time limit exceeded
2 Halted 0 ms 0 KB -