# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1100293 |
2024-10-13T12:42:00 Z |
michified |
Balloons (CEOI11_bal) |
C++17 |
|
757 ms |
6564 KB |
#include <bits/stdc++.h>
#define ll long long
#define db double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
const ll mod = 1e9 + 7;
db bestR(db x1, db r1, db x2, db r2) {
db l = 0, r = r2 + 1;
while (l < r - 0.0000001) {
db mid = (l + r) / 2;
if (sqrt((x2 - x1) * (x2 - x1) + abs(r1 - mid) * abs(r1 - mid)) >= r1 + mid) l = mid;
else r = mid;
}
return min(r2, l);
}
int main() {
// ifstream cin("balancing.in");
// ofstream cout("balancing.out");
int n, i;
cin >> n;
vector<db> x(n), r(n);
for (i = 0; i < n; i++) cin >> x[i] >> r[i];
vector<db> ans(n);
stack<int> st;
ans[0] = r[0];
st.push(0);
for (i = 1; i < n; i++) {
db res = r[i];
while (not st.empty()) {
res = min(res, bestR(x[st.top()], ans[st.top()], x[i], r[i]));
if (res >= ans[st.top()]) st.pop();
else break;
}
ans[i] = res;
st.push(i);
}
cout << fixed << setprecision(3);
for (i = 0; i < n; i++) cout << ans[i] << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
10 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
2 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
336 KB |
505 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
336 KB |
2000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
848 KB |
20000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
1984 KB |
50000 numbers |
2 |
Correct |
195 ms |
1736 KB |
49912 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
334 ms |
3656 KB |
100000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
378 ms |
4168 KB |
115362 numbers |
2 |
Correct |
444 ms |
3928 KB |
119971 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
5204 KB |
154271 numbers |
2 |
Correct |
751 ms |
6120 KB |
200000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
644 ms |
6564 KB |
200000 numbers |
2 |
Incorrect |
757 ms |
6216 KB |
199941st numbers differ - expected: '80461337.7310000062', found: '80461337.7619999945', error = '0.0309999883' |
3 |
Halted |
0 ms |
0 KB |
- |