Submission #1262083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262083		inkvizytor	Mixture (BOI20_mixture)	C++20	0 / 100	0 ms	324 KiB

Mixture

#include <bits/stdc++.h>
using namespace std;

#define ll long long

class mojset {
private:
    multiset<double> angles;
    multiset<double> gaps;

    static double dist(double a, double b) {
        if (b >= a) return b - a;
        return M_PI*2 - a + b;
    }

public:
    void add(double angle) {
        if (angles.count(angle)) {
            angles.insert(angle);
            return;
        }

        if (angles.empty()) {
            angles.insert(angle);
            return;
        }

        auto it = angles.lower_bound(angle);
        auto nxt = (it == angles.end() ? angles.begin() : it);
        auto prv = (it == angles.begin() ? prev(angles.end()) : prev(it));
        auto x = gaps.find(dist(*prv, *nxt));
        if (x != gaps.end()) {
            gaps.erase(x);
        } 

        gaps.insert(dist(*prv, angle));
        gaps.insert(dist(angle, *nxt));

        angles.insert(angle);
    }

    void remove(double angle) {
        auto it = angles.find(angle);
        if (it == angles.end()) return;

        if (angles.size() == 1 || angles.count(angle)) {
            angles.erase(it);
            return;
        }

        auto nxt = next(it);
        if (nxt == angles.end()) nxt = angles.begin();
        auto prv = (it == angles.begin() ? prev(angles.end()) : prev(it));

        gaps.erase(gaps.find(dist(*prv, angle)));
        gaps.erase(gaps.find(dist(angle, *nxt)));

        gaps.insert(dist(*prv, *nxt));

        angles.erase(it);
    }

    double maxGap() const {
        if (angles.size() < 2) return M_PI*2;
        return *gaps.rbegin();
    }
};


ll sqlen(ll x, ll y, ll z) {
    return x*x+y*y+z*z;
}

ll dot(ll x, ll y, ll z, ll a, ll b, ll c) {
    return x*a+y*b+z*c;
}

pair<ll, ll> conv(ll x, ll y, ll z, ll a, ll b, ll c) {
    ll l = sqlen(a, b, c);
    ll d = dot(x, y, z, a, b, c);
    return {x*l-a*d, y*l-b*d}; 
}

void wyn(int i1, int i2, mojset &s) {
    if (i1) {
        cout << 1 << '\n';
        return;
    }
    if (i2) {
        cout << 2 << '\n';
        return;
    }
    if (s.maxGap() < M_PI) {
        cout << 3 << '\n';
        return;
    }
    cout << 0 << '\n';
}

ll nwd(ll a, ll b) {
    if (a==b && a==0){
        return 1;
    }
    if (a < b) {
        swap(a, b);
    }
    if (b == 0) {
        return a;
    }
    return nwd(b, a%b);
}

int main() {
	ios::sync_with_stdio(0); 
    cin.tie(0);
    ll a, b, c;
    cin >> a >> b >> c;
    ll n;
	cin >> n;
    vector<pair<ll, pair<ll, ll>>> w = {{0, {0, 0}}};
    mojset s;
    int ile1 = 0;
    int ile2 = 0;
    map<pair<ll, ll>, int> mp;
    for (int i = 0; i < n; i++) {
        char q;
        cin >> q;
        if (q == 'A') {
            ll x, y, z;
            cin >> x >> y >> z;
            pair<ll ,ll> p = conv(x, y, z, a, b, c);
            ll d = nwd(abs(p.first), abs(p.second));
            p.first /= d;
            p.second /= d;
            w.push_back({0, p});
            if (p.first == 0 && p.second==0) {
                ile1++;
            }
            mp[p]++;
            if (mp[{-p.first, -p.second}] && (mp[p]==1)) {
                ile2++;
            }
            if (sqlen(p.first, p.second, 0) != 0) {
                double k = (double)p.first/sqrt(sqlen(p.first, p.second, 0));
                double k1 = acos(k);
                if (p.second < 0) {
                    k1 = M_PI*2-k1;
                }
                w[w.size()-1].first = k1;
                s.add(k1);
            }
            wyn(ile1, ile2, s);
        }
        else {
            int j;
            cin >> j;
            pair<ll, ll> p = w[j].second;
            if (p.first == 0 && p.second==0) {
                ile1--;
            }
            mp[p]--;
            if (mp[{-p.first, -p.second}] && (mp[p]==0)) {
                ile2--;
            }
            if (sqlen(p.first, p.second, 0) != 0) {
                double k = w[j].first;
                s.remove(k);
            }
            wyn(ile1, ile2, s);
        }
    }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40