Submission #1270734

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

Mixture

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

/*--------------------*/
/*  Mixture 2.0       */
/*--------------------*/

struct Vec {
    long long s, p, g;
};

// Hàm rút gọn vector theo tỉ lệ
Vec normalize(Vec v) {
    long long g = std::gcd(v.s, std::gcd(v.p, v.g));
    if (g > 0) {
        v.s /= g;
        v.p /= g;
        v.g /= g;
    }
    return v;
}

// Kiểm tra 2 vector cùng phương
bool sameDir(const Vec& a, const Vec& b) {
    return (a.s * b.p == a.p * b.s) &&
           (a.s * b.g == a.g * b.s) &&
           (a.p * b.g == a.g * b.p);
}

// Kiểm tra có thể biểu diễn fav bằng 1 bottle
bool can1(const Vec& fav, const Vec& v) {
    return sameDir(fav, v);
}

// Kiểm tra có thể biểu diễn fav bằng 2 bottles
bool can2(const Vec& fav, const Vec& a, const Vec& b) {
    // giải hệ tuyến tính: tồn tại x,y > 0 sao cho x*a + y*b cùng phương với fav?
    // Ta chỉ cần kiểm tra rank của ma trận (a,b,fav)
    long long M[3][3] = {
        {a.s, b.s, fav.s},
        {a.p, b.p, fav.p},
        {a.g, b.g, fav.g}
    };
    // Nếu rank({a,b,fav}) = rank({a,b}) thì có nghiệm
    auto det2 = [&](long long x1,long long y1,long long x2,long long y2){
        return x1*y2 - x2*y1;
    };
    // rank({a,b})
    bool dep = sameDir(a,b);
    // check fav trong span(a,b)
    if (!dep) {
        // xét 2 bất kỳ cặp
        // dùng a,b làm basis, kiểm tra fav có nằm trong span
        // Sử dụng định thức 3x3
        long long d1 = a.s*(b.p*fav.g - b.g*fav.p)
                     - a.p*(b.s*fav.g - b.g*fav.s)
                     + a.g*(b.s*fav.p - b.p*fav.s);
        return d1 == 0;
    } else {
        // a,b cùng phương, span chỉ 1 chiều
        return sameDir(fav, a);
    }
}

// Kiểm tra có thể biểu diễn fav bằng 3 bottles
bool can3(const Vec& fav, const Vec& a, const Vec& b, const Vec& c) {
    // chỉ cần fav nằm trong span(a,b,c)
    long long det = 
        a.s * (b.p * c.g - b.g * c.p) -
        a.p * (b.s * c.g - b.g * c.s) +
        a.g * (b.s * c.p - b.p * c.s);
    if (det == 0) {
        // span có rank < 3, giảm về 2
        return can2(fav,a,b) || can2(fav,a,c) || can2(fav,b,c);
    } else {
        return true;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Vec fav;
    cin >> fav.s >> fav.p >> fav.g;
    fav = normalize(fav);

    int N; cin >> N;

    vector<Vec> shelf;
    vector<bool> alive;
    shelf.reserve(N+5);
    alive.reserve(N+5);

    for (int qi=0; qi<N; qi++){
        char typ; cin >> typ;
        if (typ=='A'){
            Vec v; cin >> v.s >> v.p >> v.g;
            v = normalize(v);
            shelf.push_back(v);
            alive.push_back(true);
        } else {
            int idx; cin >> idx;
            alive[idx-1] = false;
        }

        // kiểm tra kết quả
        // bước brute force (O(M^3)) với M = số chai còn lại
        vector<Vec> arr;
        for (size_t i=0;i<shelf.size();i++) if (alive[i]) arr.push_back(shelf[i]);

        int ans=0;
        // check 1
        for (auto &v:arr){
            if (can1(fav,v)){ ans=1; break;}
        }
        // check 2
        if (!ans){
            for (size_t i=0;i<arr.size();i++){
                for (size_t j=i+1;j<arr.size();j++){
                    if (can2(fav,arr[i],arr[j])){ ans=2; break;}
                }
                if (ans) break;
            }
        }
        // check 3
        if (!ans){
            for (size_t i=0;i<arr.size();i++){
                for (size_t j=i+1;j<arr.size();j++){
                    for (size_t k=j+1;k<arr.size();k++){
                        if (can3(fav,arr[i],arr[j],arr[k])){ ans=3; break;}
                    }
                    if (ans) break;
                }
                if (ans) break;
            }
        }

        cout << ans << "\n";
    }
}

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