제출 #1307985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307985		orzorzorz	Mixture (BOI20_mixture)	C++20	0 / 100	1 ms	572 KiB

Mixture

/**
 * BOI 2020 - Mixture
 * * 解法重點：
 * 1. 投影到 2D 平面：計算相對於目標比例的偏差向量 (x, y)。
 * 2. 優先級判斷：
 * - 1: 存在 (0,0) 向量。
 * - 2: 存在一對相反向量 (v, -v)。
 * - 3: 向量角度覆蓋原點 (最大相鄰夾角 < 180度)。
 * - 0: 其他。
 * 3. 使用 multiset 動態維護角度間隙。
 */

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

// 定義常數與型別
const long double PI = acos(-1.0);
const long double EPS = 1e-14;

// 儲存每一瓶的資訊，用於刪除時回溯
struct BottleInfo {
    long long x, y; // 投影後的 2D 向量
    long double ang; // 極角
    bool is_pure;    // 是否是完美比例 (0,0)
};

// 全域變數維護狀態
long long Tf_s, Tf_p, Tf_g; // 目標成分
long long Tf_sum;           // 目標總重

vector<BottleInfo> history; // 記錄第 i 次加入的瓶子資訊 (index 1-based)

// 狀態計數器
int cnt_pure = 0; // 完美比例瓶子的數量
int cnt_opp = 0;  // 相反向量對的數量 (Case 2)

// 幾何資料結構
map<pair<long long, long long>, int> vec_map; // 儲存標準化向量計數
map<long double, int> ang_map;                // 儲存角度計數
multiset<long double> gaps;                   // 儲存相鄰角度的間隙

// 計算最大公因數
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 輔助函數：增加間隙
void add_gap(long double g) {
    gaps.insert(g);
}

// 輔助函數：移除間隙
void remove_gap(long double g) {
    auto it = gaps.find(g);
    if (it != gaps.end()) {
        gaps.erase(it);
    }
}

// 處理角度增加
void add_angle(long double ang) {
    if (ang_map.empty()) {
        ang_map[ang]++;
        add_gap(2 * PI);
        return;
    }

    // 如果角度已存在，只增加計數，幾何結構不變
    if (ang_map.count(ang)) {
        ang_map[ang]++;
        return;
    }

    // 尋找插入位置的前驅與後繼
    auto it = ang_map.upper_bound(ang);
    long double nxt_ang, prv_ang;

    if (it == ang_map.end()) {
        nxt_ang = ang_map.begin()->first;
        prv_ang = ang_map.rbegin()->first;
    } else {
        nxt_ang = it->first;
        if (it == ang_map.begin()) {
            prv_ang = ang_map.rbegin()->first;
        } else {
            prv_ang = prev(it)->first;
        }
    }

    // 移除舊間隙
    long double old_gap = nxt_ang - prv_ang;
    if (old_gap < 0) old_gap += 2 * PI;
    remove_gap(old_gap);

    // 加入新間隙
    long double g1 = ang - prv_ang;
    if (g1 < 0) g1 += 2 * PI;
    long double g2 = nxt_ang - ang;
    if (g2 < 0) g2 += 2 * PI;

    add_gap(g1);
    add_gap(g2);

    ang_map[ang]++;
}

// 處理角度移除
void remove_angle(long double ang) {
    ang_map[ang]--;
    if (ang_map[ang] > 0) return;

    // 計數歸零，移除該角度
    ang_map.erase(ang);

    if (ang_map.empty()) {
        gaps.clear();
        return;
    }

    // 尋找鄰居 (邏輯與 add 類似，但注意 ang 已從 map 移除)
    auto it = ang_map.upper_bound(ang);
    long double nxt_ang, prv_ang;

    if (it == ang_map.end()) {
        nxt_ang = ang_map.begin()->first;
    } else {
        nxt_ang = it->first;
    }

    if (it == ang_map.begin()) {
        prv_ang = ang_map.rbegin()->first;
    } else {
        prv_ang = prev(it)->first;
    }

    // 移除兩個小間隙
    long double g1 = ang - prv_ang;
    if (g1 < 0) g1 += 2 * PI;
    long double g2 = nxt_ang - ang;
    if (g2 < 0) g2 += 2 * PI;
    
    remove_gap(g1);
    remove_gap(g2);

    // 恢復大間隙
    long double new_gap = nxt_ang - prv_ang;
    if (new_gap < 0) new_gap += 2 * PI;
    add_gap(new_gap);
}

// 處理新增瓶子
void add_bottle(long long s, long long p, long long g) {
    long long sum = s + p + g;
    // 投影轉換：val * Tf_sum - target * sum
    long long dx = s * Tf_sum - Tf_s * sum;
    long long dy = p * Tf_sum - Tf_p * sum;
    // z 分量是相依的，不需要計算

    BottleInfo info;
    info.is_pure = false;
    info.x = dx; 
    info.y = dy;

    if (dx == 0 && dy == 0) {
        info.is_pure = true;
        cnt_pure++;
    } else {
        // 計算標準化向量 (用於 Case 2)
        long long common = gcd(abs(dx), abs(dy));
        dx /= common;
        dy /= common;
        
        // 檢查是否存在相反向量 (-dx, -dy)
        if (vec_map.count({-dx, -dy}) && vec_map[{-dx, -dy}] > 0) {
            cnt_opp++;
        }
        vec_map[{dx, dy}]++;

        // 計算角度並維護 Gaps (用於 Case 3)
        info.ang = atan2((long double)dy, (long double)dx);
        add_angle(info.ang);
    }
    history.push_back(info);
}

// 處理移除瓶子
void remove_bottle(int idx) {
    // idx 是 1-based，轉為 0-based
    BottleInfo info = history[idx - 1]; 

    if (info.is_pure) {
        cnt_pure--;
    } else {
        long long dx = info.x;
        long long dy = info.y;
        long long common = gcd(abs(dx), abs(dy));
        dx /= common;
        dy /= common;

        vec_map[{dx, dy}]--;
        // 檢查是否移除了配對中的一個
        if (vec_map.count({-dx, -dy}) && vec_map[{-dx, -dy}] > 0) {
            cnt_opp--;
        }

        remove_angle(info.ang);
    }
}

// 查詢答案
int query() {
    if (cnt_pure > 0) return 1;
    if (cnt_opp > 0) return 2;
    
    // Case 3: 檢查是否包圍原點
    if (gaps.empty()) return 0;
    
    // 如果最大間隙 < PI，則所有點圍繞原點
    // 浮點數比較需要 EPS，但這裡用 < PI - EPS 確保嚴格小於
    if (*gaps.rbegin() < PI - EPS) return 3;

    return 0;
}

int main() {
    // 優化 IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 讀取目標
    if (!(cin >> Tf_s >> Tf_p >> Tf_g)) return 0;
    Tf_sum = Tf_s + Tf_p + Tf_g;

    int n;
    cin >> n;

    while (n--) {
        char type;
        cin >> type;
        if (type == 'A') {
            long long s, p, g;
            cin >> s >> p >> g;
            add_bottle(s, p, g);
        } else {
            int idx;
            cin >> idx;
            remove_bottle(idx);
        }
        cout << query() << "\n";
    }

    return 0;
}

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