Submission #891239

#	Time	Username	Problem	Language	Result	Execution time	Memory
891239		fragadmsc	Balloons (CEOI11_bal)	C++14	100 / 100	393 ms	15452 KiB

bal

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<long long, long long> pii;
typedef long long ll;
typedef long double ld;
 
const long long MAXLOG = 23;
const long long MAXN = 1e3+5; // use com cuidado
const long long MOD = 998244353;
const long long inf = 1e9 + 10;
const long long TWO_MOD_INV = 500000004;
 
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define KAMEKAMEHA ios_base::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz(x) (int)x.size()

int main() {
    KAMEKAMEHA
    #ifdef FRAGA     
        //freopen("output.out", "w", stdout);
        freopen("err.er", "w", stderr);
    #endif 
    #ifndef FRAGA
        //freopen("cbarn2.in", "r", stdin);
        //freopen("cbarn2.out", "w", stdout);
    #endif
    ll n;
    cin>>n;
    vector<pair<ld, ld>> vet(n+2);
    for(ll i=1;i<=n;i++) {
        cin>>vet[i].f>>vet[i].s;
    }
    vet[0]={-1e10, 2*1e9};
    stack<ll> st;
    st.push(0);
    vector<ld> rad(n+5);
    ll ult;
    for(ll i=1;i<=n;i++) {
        ult=0;
        while(true) {
            //n bateu
            if(vet[i].s<(vet[i].f-vet[st.top()].f)*(vet[i].f-vet[st.top()].f)/(4.0*vet[st.top()].s)) {
                if(vet[i].s<vet[st.top()].s) {// n bateu e eh menor, ja pode encerrar
                    rad[i]=vet[i].s;
                    if(ult!=0) st.push(ult);
                    st.push(i);
                    break;
                } else { //n bateu mas e maior, elimina o ult e continua
                    st.pop();
                }
            } else { //bateu
                //muda pra um raio menor e ve se vai ter um pra deixar o raio menor ainda 
                vet[i].s=(vet[i].f-vet[st.top()].f)*(vet[i].f-vet[st.top()].f)/(4.0*vet[st.top()].s);
                ult=st.top();
                st.pop();
            }
        }
        
    }
    for(ll i=1;i<=n;i++) {
        cout<<fixed<<setprecision(6)<<rad[i]<<endl;
    }
    cout<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10