Submission #349668

#TimeUsernameProblemLanguageResultExecution timeMemory
349668silverfishBalloons (CEOI11_bal)C++14
100 / 100
352 ms12652 KiB
#include <bits/stdc++.h> using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; } struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; string _ARR_(int* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef unsigned int uint; typedef pair<int, int> pii; //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) #define ar array const int INF = 1e9 + 7, N = 2e5; ld r[N], x[N]; int n; int best[N]; ld getdiff(int i, int j){ return (x[j] - x[i])*(x[j] - x[i])/(4*r[i]); } void find_first(int i, int j, int cur){ int lo = cur, hi = n-1; if(getdiff(i, n-1) < getdiff(j, n-1)) return; while(hi - lo > 0){ int m = (lo + hi) / 2; if(getdiff(i, m) < getdiff(j, m)) lo = m+1; else hi = m; } if(~best[lo]){ if(getdiff(j, lo) < getdiff(best[lo], lo)){ find_first(j, best[lo], lo); best[lo] = j; }else{ find_first(best[lo],j, lo); } }else{ best[lo] = j; } return; } int main(void) { FAST; cout << fixed << setprecision(3); cin >> n; fill(best, best+n, -1); for(int i = 0; i < n; ++i){ cin >> x[i] >> r[i]; } cout << r[0] << '\n'; r[1] = min(r[1], getdiff(0, 1)); cout << r[1] << '\n'; best[1] = 0; for(int i = 2; i < n; ++i){ vector<pair<ld, int>> v; if(~best[i]) v.pb({getdiff(best[i], i), best[i]}); v.pb({getdiff(i-1, i), i-1}); v.pb({getdiff(best[i-1], i), best[i-1]}); sort(v.begin(), v.end()); find_first(v[0].second, v[1].second, i); if(~best[i]) find_first(v[0].second, v[2].second, i); best[i] = v[0].second; r[i] = min(r[i], getdiff(best[i], i)); cout << r[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...