oj.uz

Submission #866258

# Submission time Handle Problem Language Result Execution time Memory
866258 2023-10-25T16:22:14 Z dio_2 Balloons (CEOI11_bal) C++17
40 / 100
 2000 ms 7888 KB 
#include<bits/stdc++.h>
using namespace std;

using ld = long double;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin >> N;
	
	vector<int> x(N), r(N);
	vector<ld> ans(N);
	
	for(int i = 0;i < N;i++){
		cin >> x[i] >> r[i];
	}
	
	ans[0] = r[0];
	cout << fixed << setprecision(3) << ans[0] << '\n';
	
	#define X first
	#define Y second
	auto d = [&](pair<ld, ld> A, pair<ld, ld> B)->ld{
		return (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y);
	};
	
	/*
	3
	0 9
	8 1
	13 7
	*/
	auto Calc = [&](int i, int j)->ld{
		ld radius_j = ans[j];
		pair<ld, ld> centre_j = {x[j], radius_j};
	
		ld lo = 0, hi = r[i], mid;
		
		for(int rep = 0;rep < 70;++rep){
			mid = (lo + hi) / 2;
			ld radius_i = mid;
			pair<ld, ld> centre_i = {x[i], radius_i};
			if(d(centre_i, centre_j) >= (radius_i + radius_j) * (radius_i + radius_j))
				lo = mid;
			else 
				hi = mid;
		}
		
		return (lo + hi) / 2;
	};
	
	for(int i = 1;i < N;i++){
		ld use = r[i];
		for(int j = 0;j < i;j++){
			use = min(use, Calc(i, j));
		}
		ans[i] = use;
		cout << fixed << setprecision(3) << use << '\n';
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 448 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1694 ms 760 KB 2000 numbers

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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