oj.uz

Submission #961800

# Submission time Handle Problem Language Result Execution time Memory
961800 2024-04-12T13:13:40 Z akkshaysr Balloons (CEOI11_bal) C++17
100 / 100
 118 ms 10140 KB 
#include <bits/stdc++.h>
#define fr first
#define se second
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define repr(i,a,b) for(int i = a; i > (b); --i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IN(i,l,r) (l<i&&i<r)
#define pb push_back
#define dbg(v) \
	cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
const int U = 2e5+2;
int n;
vi x,r;
vector<ld> final_r;

ld norm(int x1,int y1,int x2,int y2){
    return ((ld)x1 - x2)*((ld)x1 - x2) + ((ld)y1 - y2)*((ld)y1 - y2);
}

ld get_radius(int x1,int x2,ld r1){
    return norm(x1,0,x2,0)/(4*r1);
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
    cin >> n;
    x = vi(n,0); r = vi(n,0); final_r = vector<ld>(n,0);
    rep(i,0,n){
        cin >> x[i] >> r[i];
    }
    stack<int> ib;
    rep(i,0,n){
        ld fr = r[i];
        while(!ib.empty()){
            int j = ib.top();
            fr = min(fr,get_radius(x[i],x[j],final_r[j]));
            if(fr >= final_r[j]) ib.pop();
            else break;
        }
        final_r[i] = fr;
        ib.push(i);
    }
    cout << fixed << setprecision(3);
    for(auto &r : final_r) cout << r << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB 10 numbers

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1116 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2560 KB 50000 numbers
2 Correct 27 ms 3160 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4692 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 5200 KB 115362 numbers
2 Correct 73 ms 6220 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6708 KB 154271 numbers
2 Correct 106 ms 10140 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 8272 KB 200000 numbers
2 Correct 106 ms 10064 KB 199945 numbers