Submission #1264984

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

Mixture

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

long long GCD(long long a, long long b)
{
    long long t;
    while (b > 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

long long s, g, p, q;

void Inp()
{
    cin >> s >> g >> p >> q;
}

struct Bottle
{
    long long a, b, c;

    Bottle() = default;

    Bottle(long long _a, long long _b, long long _c)
    {
        long long d = GCD(GCD(_a, _b), _c);
        a = _a / d;
        b = _b / d;
        c = _c / d;
    }

    bool operator == (const Bottle& other) const
    {
        return (this->a == other.a) && (this->b == other.b) && (this->c == other.c);
    }
};

int n;
Bottle arr[MaxN];

struct Fraction
{
    long long a, b;

    Fraction(long long _a, long long _b)
    {
        a = _a;
        b = _b;
    }

    Fraction& operator = (const Fraction& other)
    {
        this->a = other.a;
        this->b = other.b;
        return *this;
    }

    bool operator == (const Fraction& other) const
    {
        return this->a * other.b == this->b * other.a;
    }

    bool operator < (const Fraction& other) const
    {
        return (long double)((long double)this->a / this->b) < (long double)((long double)other.a / other.b);
    }

    bool operator > (const Fraction& other) const
    {
        return (long double)((long double)this->a / this->b) > (long double)((long double)other.a / other.b);
    }
};

int cnts, cntt;
int cnt[2][2];
Bottle sam;
map<Fraction, int> frac[2];
multiset<Fraction> fr[2];
long long cnts2;

void Add(bool rev, int p)
{
    cntt += rev * (-1) + (!rev);
    long long a = (arr[p].a * sam.b - arr[p].b * sam.a), b = (arr[p].b * sam.c - arr[p].c * sam.b);
    //cout << a << " " << b << endl;
    if (a == 0 && b == 0)
    {
        cnts += rev * (-1) + (!rev);
        return;
    }
    if (a == 0)
    {
        cnt[0][b < 0] += rev * (-1) + (!rev);
        return;
    }
    if (b == 0)
    {
        cnt[1][a < 0] += rev * (-1) + (!rev);
        return;
    }
    Fraction f = Fraction(b, a);
    if (!rev)
    {
        frac[a < 0][f]++;
        cnts2 += frac[a > 0][f];
        fr[a < 0].insert(f);
    }
    else
    {
        frac[a < 0][f]--;
        cnts2 -= frac[a > 0][f];
        fr[a < 0].erase(fr[a < 0].lower_bound(f));
    }
}

bool Check2()
{
    if (cntt < 2)
    {
        return false;
    }
    if (cnt[0][0] > 0 && cnt[0][1] > 0)
    {
        return true;
    }
    if (cnt[1][0] > 0 && cnt[1][1] > 0)
    {
        return true;
    }
    return cnts2 > 0;
}

bool Check3()
{
    if (cntt < 3)
    {
        return false;
    }
    if (fr[0].empty())
    {
        return false;
    }
    auto p = fr[1].lower_bound(*fr[0].begin()), q = fr[1].lower_bound(*(--fr[0].end()));
    if (p != q)
    {
        return true;
    }
    p = fr[0].lower_bound(*fr[1].begin());
    q = fr[0].lower_bound(*(--fr[1].end()));
    return p != q;
}

void Exc()
{
    long long d = GCD(GCD(s, g), p);
    s /= d;
    g /= d;
    p /= d;
    sam = Bottle(s, g, p);
    cnts = n = 0;
    for (int x = 1; x <= q; x++)
    {
        //cout << x << endl;
        char t;
        cin >> t;
        if (t == 'A')
        {
            n++;
            long long a, b, c;
            cin >> a >> b >> c;
            arr[n] = Bottle(a, b, c);
            Add(false, n);
        }
        else
        {
            int p;
            cin >> p;
            Add(true, p);
        }
        if (cnts > 0)
        {
            cout << 1 << "\n";
            continue;
        }
        if (Check2())
        {
            cout << 2 << "\n";
            continue;
        }
        if (Check3())
        {
            cout << 3 << "\n";
            continue;
        }
        cout << 0 << "\n";
    }
}

int main()
{
    //freopen("MIXTURE.INP", "r", stdin);
    //freopen("MIXTURE.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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