Submission #772277

#	Time	Username	Problem	Language	Result	Execution time	Memory
772277		hanlulu	Balloons (CEOI11_bal)	C++14	100 / 100	148 ms	8788 KiB

bal

/*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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10