oj.uz

Submission #772277

# Submission time Handle Problem Language Result Execution time Memory
772277 2023-07-03T21:12:44 Z hanlulu Balloons (CEOI11_bal) C++14
100 / 100
 148 ms 8788 KB 
/*https://oj.uz/problem/view/CEOI11_bal
first, if pre ballon radius is R, positon is x, new radius is r, position is y
we got (R+r)^2= (R-r)^2 +(y-x)^2  => r= (y-x)^2/ 4R
sort by position, for each ballon, if it's radius bigger than pre ones, the pre ones will never impact future one
so, we use stack save all radius, for new one , compare all ones in stack, compare with them find the real R.
for each new R, if it's bigger than pre one, pop pre one. 
 */
#include <bits/stdc++.h>
using namespace std;
double getr(double lastx,double lastr,double x){
	return (x-lastx) * (x-lastx) / 4 / lastr;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);	
	cout.tie(0);
 	//freopen("hayfeast.in","r",stdin);
 	//freopen("hayfeast.out","w",stdout);
 	int n;
 	cin >> n ;
 	vector <double> ans(n);//save answer
 	stack<pair<double,double>> st;//first, x second, r
	double x,r;//r is limitation for radius
	for (int i = 0; i < n; i++) {
		cin >> x >> r;
		while (!st.empty()) {
			double lastr = st.top().second;
			double lastx = st.top().first;
			double maxr = getr(lastx,lastr,x);
			r = min(r,maxr);
			if (r > lastr) {
			//bigger than last, last is useless,next time will check pre pre one to find new r
				st.pop();
			}
			else break;//smaller tha preone,no need to check others 
		}		
		st.push({x,r});
		ans[i] = r;
	}
	
	
	cout << fixed << setprecision(3) ;
	for (auto t:ans) cout << t << '\n';	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2024 KB 50000 numbers
2 Correct 36 ms 2380 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3488 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4080 KB 115362 numbers
2 Correct 86 ms 5252 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5232 KB 154271 numbers
2 Correct 148 ms 8788 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 6192 KB 200000 numbers
2 Correct 140 ms 8628 KB 199945 numbers