Submission #1097425

#TimeUsernameProblemLanguageResultExecution timeMemory
1097425StillOnQiCondensationBalloons (CEOI11_bal)C++14
40 / 100
380 ms11404 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define all(x) (x).begin(), (x).end() #define inf 1000000007ll #define llmax LLONG_MAX #define pi 3.141592653589793238462643383279502884197169399 long long binpow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } ll ncr(int n, int r) { if (n < r) return 0; long long p = 1, k = 1; if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; long long m = __gcd(p, k); p /= m; k /= m; n--; r--; } } else p = 1; return p; } vector <ll> vcreate(int n){ vector <ll> v(n); for (int i = 0; i < n; i++) { cin>>v[i]; } return v; } int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1}; const int MOD=998244353; ll ModExp(ll x, ll n, ll m) { assert(n >= 0); x %= m; // note: m * m must be less than 2^63 to avoid ll overflow ll res = 1; while (n > 0) { if (n % 2 == 1) { res = res * x % m; } x = x * x % m; n /= 2; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* freopen("prime_subtractorization_input.txt", "r", stdin); freopen("output.txt", "w", stdout); */ /* ll T; cin>>T; for(ll oo=0; oo<T; oo++) { } */ int n{}; cin>>n; vector<pair<long double,long double>> v(n); vector<long double> fin(n,inf*inf); for(int i{0}; i<n; i++) { cin>>v[i].first>>v[i].second; } stack<pair<long double,long double>> st; for(int i{0}; i<n; i++) { while(!st.empty()) { long double d=v[i].first-st.top().first; long double alr=(d*d)/(4*st.top().second); // max allowed radius till it touches the ballon at the top. alr=min(alr,v[i].second); if(alr<st.top().second) { fin[i]=min(alr,fin[i]); break; } fin[i]=min(alr,fin[i]); st.pop(); } if(fin[i]==inf*inf)fin[i]=v[i].second; st.push({v[i].first,fin[i]}); } cout<<fixed<<setprecision(3); for(auto u: fin)cout<<u<<endl; }
#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...