Submission #762665

#	Time	Username	Problem	Language	Result	Execution time	Memory
762665		Sig0001	Balloons (CEOI11_bal)	C++17	100 / 100	128 ms	8524 KiB

bal

#include <bits/stdc++.h>
using namespace std;

double maxRadius(int x1, int x2, double r1) {
	/**
	 * (x2 - x1)^2 + (r2 - r1)^2 = (r2 + r1)^2
	 * (x2 - x1)^2 = 4 r1 r2
	 */
	return 1LL * (x2 - x1) * (x2 - x1) / (4 * r1);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n; cin >> n;
	vector<pair<int, double>> a(n);  // [x, maxRadius]
	for (auto &[x, r]: a) cin >> x >> r;

	stack<pair<int, double>> st;  // [position, radius]
	cout << fixed << setprecision(3);

	for (int i = 0; i < n; i++) {
		auto [x2, maxR2] = a[i];
		double r2 = maxR2;
		while (not st.empty()) {
			auto [x1, r1] = st.top();
			r2 = min(r2, maxRadius(x1, x2, r1));
			if (r2 < r1) break;
			st.pop();
		}
		st.emplace(x2, r2);
		cout << r2 << '\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