Submission #1122271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122271		Leyna	Balloons (CEOI11_bal)	C++17	0 / 100	115 ms	11208 KiB

bal

#include <bits/stdc++.h>

using namespace std;

set<pair<float, int>> steigungen;
set<pair<float, int>> endpunkt;
vector<float> ende;
vector<float> steigung;

float max_r(float r1, float x1, float x2){
    return ((x1-x2) * (x1-x2)) / (4 * r1);
}

int find_interval(float x1){
    pair<int, int> interval = *lower_bound(endpunkt.begin(), endpunkt.end(), make_pair(x1, 0));
    return interval.second;
}

float schnittstelle(float a1, float b1, float a2, float b2){
    float a = b2 - b1;
    float b = 2*a2*b1 - 2*a1*b2;
    float c = b2*a1*a1 - b1*a2*a2;
    //cout << "a, b, c: " << a << " " << b << " " << c << endl;
    float radikand = sqrt(b*b - 4.0 * a * c);
    //cout << radikand << endl;
    float x1 = (-b + radikand) / (2 * a);
    float x2 = (-b - radikand) / (2 * a);
    return max(x1, x2);
}

void del(int idx){
    //cout << "del: " << idx << endl;
    endpunkt.erase(endpunkt.find(make_pair(ende[idx], idx)));
    steigungen.erase(steigungen.find(make_pair(steigung[idx], idx)));
}

int main(){
    int n; cin >> n;
    vector<float> x(n), r(n);
    for (int i=0; i<n; i++){
        cin >> x[i] >> r[i];
    }
    vector<float> res(n);
    res[0] = r[0];
    //int last_idx = 0;

    ende.resize(n);
    steigung.resize(n);    
    
    ende[0] = 1e9;
    steigung[0] = res[0]*4;
    steigungen.insert(make_pair(4*res[0], 0));
    endpunkt.insert(make_pair(1e9, 0));
    for (int i=1; i<n; i++){
        //cout << "i: " << i << endl;
        //for (auto x : endpunkt) cout << x.first << " " << x.second << endl;
        int idx = find_interval(x[i]);
        //cout << "idx: " << idx << endl;
        res[i] = min(max_r(res[idx], x[idx], x[i]), (float)r[i]);
        //cout << "radius: " << res[i] << endl;
        //steigungen.erase(steigungen.end(), steigungen.upper_bound({4.0 * res[i], 0}));
        steigung[i] = res[i] * 4.0;
        // alle steileren aus steigungen UND endpunkten löschen
        //cout << steigungen.size() << " " << endpunkt.size() << endl;
        while(steigungen.size() > 0 && (*steigungen.begin()).first <= steigung[i]){
            //cout << steigungen.size() << " " << endpunkt.size() << endl;
            int idx2 = (*steigungen.begin()).second;
            del(idx2);
        }
        //cout << steigungen.size() << " " << endpunkt.size() << endl;
        if(steigungen.size() == 0){
            steigungen.insert(make_pair(res[i]*4.0, i));
            endpunkt.insert(make_pair(1e9, i));
            continue;
        }
        //cout << x[idx] << " " << steigung[idx] << " " << x[i] << " " << steigung[i] << endl;
        float s = schnittstelle(x[idx], steigung[idx], x[i], steigung[i]);
        //cout << "s: " << s << endl;
        auto interval = lower_bound(endpunkt.begin(), endpunkt.end(), make_pair(x[i], 0));
        //cout << steigungen.size() << " " << endpunkt.size() << endl;
        while((*interval).second != find_interval(s)){
            int idx2 = (*interval).second;
            interval++;
            del(idx2);
        }
        //cout << steigungen.size() << " " << endpunkt.size() << endl;
        if(steigungen.size() == 0){
            steigungen.insert(make_pair(res[i]*4.0, i));
            endpunkt.insert(make_pair(1e9, i));
            continue;
        }
        ende[i] = s;

        endpunkt.insert(make_pair(ende[i], i));
        steigungen.insert(make_pair(steigung[i], i));
    }
    for (float a : res) cout << fixed << setprecision(3) << a << endl;
}

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