Submission #1097931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097931		MateiKing80	Mixture (BOI20_mixture)	C++14	100 / 100	549 ms	24120 KiB

Mixture

#include <bits/stdc++.h>

using namespace std;

#define PI 3.1415926535
using ll = long long;

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

double getA(double x, double y, double z)
{
    if(!x && !y && !z)
        return -1;
    double a = (x - y / 2.0 - z / 2.0) / sqrt(x * x + y * y + z * z) / sqrt(1.5);
    if(a > 1)
        a = 1;
    if(a < -1)
        a = -1;
    a = acos(a);
    if(y < z)
        a = 2 * PI - a;
    return a;
}

struct point
{
    ll x, y, z;
    bool operator < (const point& p) const
    {
        return getA(x, y, z) < getA(p.x, p.y, p.z);
    }
};

double getA(point p)
{
    return getA(p.x, p.y, p.z);
}

point inv(point p)
{
    return point{-p.x, -p.y, -p.z};
}

map<point,int> m;
set<point> s;

bool solve()
{
    if(s.empty())
        return 0;
    auto it = s.begin();

    if(getA(*it) > PI)
        return 0;
    it = s.lower_bound(inv(*it));

    if(it == s.end())
        return 0;
    double hi = getA(*it);

    it --;

    if(it == s.begin())
        return 0;
    double lo = getA(*it);

    return hi - lo <= PI;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll X,Y,Z,T;
    cin >> X >> Y >> Z;
    T = X + Y + Z;

    int N;
    cin >> N;

    int num = 0;
    ll cnt = 0;
    vector<point> p(N + 1);
    vector<double> a(N + 1);

    p[0] = point{0, 0, 0};
    while(N --)
    {
        char C;
        cin >> C;

        ll x, y, z, t, g;
        if(C == 'A')
        {
            cin >> x >> y >> z;
            t = x + y + z;
            x = x * T - X *t, y = y * T - Y * t, z = z * T -Z * t;
            g = gcd(gcd(x,y), z);
            x /= g, y /= g, z /= g;
            p[++ num] = point{x, y, z};
            m[p[num]] ++;
            s.insert(p[num]);
            if(x || y || z)
                cnt += m[inv(p[num])];
        }
        if(C == 'R')
        {
            cin >> t;
            m[p[t]] --;
            if(!m[p[t]])
                s.erase(p[t]);
            if(p[t].x || p[t].y || p[t].z)
                cnt -= m[inv(p[t])];
        }
        if(m[p[0]])
            cout << 1 << '\n';
        else if(cnt)
            cout << 2 << '\n';
        else if(solve())
            cout << 3 << '\n';
        else
            cout << 0 << '\n';
    }
}

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