oj.uz

Submission #394267

# Submission time Handle Problem Language Result Execution time Memory
394267 2021-04-26T09:24:11 Z KoD Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 204 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -