oj.uz

Submission #1073888

# Submission time Handle Problem Language Result Execution time Memory
1073888 2024-08-25T02:01:52 Z vjudge1 Mobile (BOI12_mobile) C++17
70 / 100
 1000 ms 57868 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	ld L;
	cin >> n >> L;
	vector <pair<ld,ld>> pts;
	for(int i=0; i<n; i++){
		ld x, y;
		cin >> x >> y;
		if(!pts.empty() && x == pts.back().first){
			pts.back().second = min(pts.back().second, abs(y));
		}
		else{
			pts.push_back({x, abs(y)});
		}
	}
	n = pts.size();

	const ld EPS = 1e-4;
	ld l=0, r=3e9, mid;
	while(r-l>EPS){
		mid = (l+r)/2;

		vector <pair<ld,ld>> seg;

		for(int i=0; i<n; i++){
			ld x = pts[i].first, y = pts[i].second;
			if(mid <= y){
				continue;
			}
			ld d = sqrt(mid*mid-y*y);
			if(x-d <= L && x+d >= 0)
				seg.push_back({max((ld)0.0, x-d),min((ld)L, x+d)});
		}

		bool can = !seg.empty();
		if(can){
			sort(seg.begin(), seg.end());
			auto [st, en] = seg[0];
			for(int i=1; i<seg.size(); i++){
				auto [st2, en2] = seg[i];
				if(st2 > en){
					can = false;
					break;
				}
				en = max(en, en2);
			}
			if(abs(st)>EPS || abs(en-L) > EPS) can = false;
		}

		if(can) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(6) << l << '\n';
	return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=1; i<seg.size(); i++){
      |                 ~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5232 KB Output is correct
2 Correct 134 ms 4108 KB Output is correct
3 Correct 128 ms 3800 KB Output is correct
4 Correct 67 ms 5792 KB Output is correct
5 Correct 13 ms 1116 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1364 KB Output is correct
2 Correct 49 ms 3156 KB Output is correct
3 Correct 73 ms 5464 KB Output is correct
4 Correct 69 ms 5952 KB Output is correct
5 Correct 66 ms 6428 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 5992 KB Output is correct
2 Correct 129 ms 4040 KB Output is correct
3 Correct 248 ms 5588 KB Output is correct
4 Correct 61 ms 6828 KB Output is correct
5 Correct 35 ms 2152 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4392 KB Output is correct
2 Correct 116 ms 3996 KB Output is correct
3 Correct 64 ms 1968 KB Output is correct
4 Correct 62 ms 7320 KB Output is correct
5 Correct 86 ms 7120 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6904 KB Output is correct
2 Correct 119 ms 4012 KB Output is correct
3 Correct 65 ms 1948 KB Output is correct
4 Correct 62 ms 7572 KB Output is correct
5 Correct 85 ms 6436 KB Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 5756 KB Output is correct
2 Correct 533 ms 29520 KB Output is correct
3 Correct 437 ms 11288 KB Output is correct
4 Correct 322 ms 33600 KB Output is correct
5 Correct 411 ms 30232 KB Output is correct

Subtask #14
0 / 5.0

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

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 6268 KB Output is correct
2 Correct 661 ms 43276 KB Output is correct
3 Correct 335 ms 11460 KB Output is correct
4 Correct 383 ms 47432 KB Output is correct
5 Correct 518 ms 42060 KB Output is correct

Subtask #16
0 / 5.0

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

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 6900 KB Output is correct
2 Correct 768 ms 47288 KB Output is correct
3 Correct 572 ms 14880 KB Output is correct
4 Correct 461 ms 52564 KB Output is correct
5 Correct 591 ms 45760 KB Output is correct

Subtask #18
0 / 5.0

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

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 7588 KB Output is correct
2 Correct 893 ms 50008 KB Output is correct
3 Correct 573 ms 16104 KB Output is correct
4 Correct 598 ms 57316 KB Output is correct
5 Correct 663 ms 50212 KB Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 9364 KB Output is correct
2 Execution timed out 1018 ms 57868 KB Time limit exceeded
3 Halted 0 ms 0 KB -