Submission #394267

#	Time	Username	Problem	Language	Result	Execution time	Memory
394267		KoD	Mixture (BOI20_mixture)	C++17	0 / 100	1 ms	204 KiB

Mixture

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

using ARR = std::array<ll, 3>;

void fix(ARR& arr) {
    ll g = std::gcd(std::gcd(arr[0], arr[1]), arr[2]);
    for (auto &x: arr) {
        x /= g;
    }
}

bool same(const ARR& a, const ARR& b, const ARR& c) {
    return (a[0]*b[1]*c[2] + a[1]*b[2]*c[0] + a[2]*b[0]*c[1]) - (a[2]*b[1]*c[0] + a[1]*b[0]*c[2] + a[0]*b[2]*c[1]) == 0;
}

int main() {
    ARR G;
    for (auto& x: G) {
        std::cin >> x;
    }
    fix(G);
    int Q;
    std::cin >> Q;
    Vec<ARR> vec;
    Vec<int> qs(Q);
    for (int i = 0; i < Q; ++i) {
        char c;
        std::cin >> c;
        if (c == 'A') {
            ARR arr;
            for (auto& x: arr) {
                std::cin >> x;
            }
            fix(arr);
            vec.push_back(std::move(arr));
            qs[i] = (int) vec.size();
        }
        else {
            std::cin >> qs[i];
            qs[i] = -qs[i];
        }
    }
    const int N = (int) vec.size();
    Vec<bool> one(N);
    for (int i = 0; i < N; ++i) {
        one[i] = (vec[i] == G);
    }
    Vec<Vec<bool>> two(N, Vec<bool>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (same(vec[i], vec[j], G)) {
                two[i][j] = two[j][i] = true;
            }
        }
    }
    std::set<int> in;
    int one_c = 0, two_c = 0;
    for (int q = 0; q < Q; ++q) {
        if (qs[q] > 0) {
            qs[q] -= 1;
            if (one[qs[q]]) {
                one_c += 1;
            }
            for (const auto x: in) {
                if (two[x][qs[q]]) {
                    two_c += 1;
                }
            }
            in.insert(qs[q]);
        }
        else {
            qs[q] = -qs[q];
            qs[q] -= 1;
            in.erase(qs[q]);
            for (const auto x: in) {
                if (two[x][qs[q]]) {
                    two_c -= 1;
                }
            }
            if (one[qs[q]]) {
                one_c -= 1;
            }
        }
        if (one_c > 0) {
            std::cout << 1 << '\n';
        }
        else if (two_c > 0) {
            std::cout << 2 << '\n';
        }
        else {
            if (in.empty()) {
                std::cout << 0 << '\n';
            }
            else {
                const int x = *in.begin();
                int y = -1;
                for (const auto t: in) {
                    if (vec[t] != vec[x]) {
                        y = t;
                        break;
                    }
                }
                if (y == -1) {
                    std::cout << 0 << '\n';
                }
                else {
                    bool ok = false;
                    for (const auto t: in) {
                        if (!same(vec[x], vec[y], vec[t])) {
                            ok = true;
                            break;
                        }
                    }
                    std::cout << (ok ? 3 : 0) << '\n';
                }
            }
        }
    }
    return 0;
}

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