oj.uz

Submission #941491

# Submission time Handle Problem Language Result Execution time Memory
941491 2024-03-09T02:20:28 Z dwuy Balloons (CEOI11_bal) C++14
10 / 100
 652 ms 10232 KB 
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long
#define double long double

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;

int n;
pdd a[MX];
pdd v[MX];

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se;
}

double sqr(double x){
    return x*x;
}

double euler(pdd a, pdd b){
    return sqrt(sqr(a.fi - b.fi) + sqr(a.se - b.se));
}

double dis(pdd ball, double p){
    double lo=0, hi=INF;
    for(int t=0; t<45; t++){
        double mid = (lo+hi)/2;
        if(euler(ball, {p, mid}) >= mid + ball.se) lo = mid;
        else hi = mid;
    }
    return (lo + hi)/2;
}

void solve(){   
    stack<pdd> v;
    for(int i=1; i<=n; i++){
        while(v.size()){
            double dist = min(dis(v.top(), a[i].fi), a[i].se);
            if(dist >= v.top().se) v.pop();
            else break;
        }
        v.push({a[i].fi, v.size()? min(dis(v.top(), a[i].fi), a[i].se) : a[i].se});
        cout << fixed << setprecision(3) << v.top().se << '\n';
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB 10 numbers

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB 2nd numbers differ - expected: '252735385.4379999936', found: '1000000000.0000000000', error = '747264614.5620000362'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB 6th numbers differ - expected: '213.0000000000', found: '238.0000000000', error = '25.0000000000'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2396 KB 79th numbers differ - expected: '36.0070000000', found: '2766.0000000000', error = '2729.9930000000'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 4700 KB 137th numbers differ - expected: '67.1010000000', found: '3129.0000000000', error = '3061.8990000000'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 4776 KB 250th numbers differ - expected: '15134.0000000000', found: '18307.0000000000', error = '3173.0000000000'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 7312 KB 162nd numbers differ - expected: '7765.0000000000', found: '14571.0000000000', error = '6806.0000000000'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 7504 KB 510th numbers differ - expected: '4505.0010000000', found: '13465.0000000000', error = '8959.9990000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 505 ms 10232 KB 161st numbers differ - expected: '1703.0000000000', found: '4036.0000000000', error = '2333.0000000000'
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 652 ms 10064 KB 248th numbers differ - expected: '2694.0020000000', found: '8658.0000000000', error = '5963.9980000000'
2 Halted 0 ms 0 KB -