Submission #1167595

#TimeUsernameProblemLanguageResultExecution timeMemory
1167595kiennguyendinhBalloons (CEOI11_bal)C++17
100 / 100
115 ms11392 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") using namespace std; struct ball{ long double x,r; }; ball a[200001]; long double res[200001]; int st[200001]; int to = 0; void pu(int pos){ st[++to] = pos; } void po(){ to--; } int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; for(int i = 1;i <= n;i++) cin >> a[i].x >> a[i].r; res[1] = a[1].r; pu(1); for(int i = 2;i <= n;i++){ res[i] = a[i].r; res[i] = min(res[i],(a[st[to]].x*a[st[to]].x - 2*a[i].x*a[st[to]].x + a[i].x*a[i].x)/(4*res[st[to]])); while(to && res[i] >= res[st[to]]){ po(); res[i] = min(res[i],(a[st[to]].x*a[st[to]].x - 2*a[i].x*a[st[to]].x + a[i].x*a[i].x)/(4*res[st[to]])); } pu(i); } for(int i = 1;i <= n;i++){ cout << fixed << setprecision(3) << res[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...