Submission

Score: 0

User: a0ms1n

Problemset: ถังดักนิวทริโน

Language: cpp

Time: 0.002 second

Submitted On: 2025-05-28 07:37:15

// เขียนโดยใช้ AI ครับ ผมจะลองเทสว่าโมเดลจะตรวจเจอไหม
// ขอโทษล่วงหน้าครับ
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <functional>

using namespace std;

struct Tank {
    int id;
    int A;
    int B;
    vector<int> children;
    int total_nested_count;
    bool is_hit;
};

bool contains(const Tank& t1, const Tank& t2) {
    return t1.A <= t2.A && t1.B >= t2.B;
}

void calculateNestedCounts(int u, vector<Tank>& tanks, const vector<vector<int>>& adj) {
    tanks[u].total_nested_count = 1;
    for (int v : adj[u]) {
        calculateNestedCounts(v, tanks, adj);
        tanks[u].total_nested_count += tanks[v].total_nested_count;
    }
}

void getCoveredHitTanks(int u, const vector<Tank>& tanks, const vector<vector<int>>& adj, vector<bool>& covered_hits) {
    if (tanks[u].is_hit) {
        covered_hits[tanks[u].id] = true;
    }
    for (int v : adj[u]) {
        getCoveredHitTanks(v, tanks, adj, covered_hits);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<Tank> tanks(N + 1);
    vector<pair<int, int>> initial_coords(N);

    for (int i = 0; i < N; ++i) {
        tanks[i + 1].id = i + 1;
        cin >> tanks[i + 1].A >> tanks[i + 1].B;
        initial_coords[i] = {tanks[i + 1].A, tanks[i + 1].B};
        tanks[i + 1].is_hit = false;
    }

    vector<int> hit_tank_ids(M);
    for (int i = 0; i < M; ++i) {
        cin >> hit_tank_ids[i];
        tanks[hit_tank_ids[i]].is_hit = true;
    }

    vector<vector<int>> adj(N + 1);
    vector<vector<int>> parent_adj(N + 1);

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j) continue;

            if (contains(tanks[i], tanks[j])) {
                bool direct_containment = true;
                for (int k = 1; k <= N; ++k) {
                    if (k == i || k == j) continue;
                    if (contains(tanks[i], tanks[k]) && contains(tanks[k], tanks[j])) {
                        direct_containment = false;
                        break;
                    }
                }
                if (direct_containment) {
                    adj[i].push_back(j);
                    parent_adj[j].push_back(i);
                }
            }
        }
    }

    tanks.assign(N + 1, Tank());
    for (int i = 0; i < N; ++i) {
        tanks[i + 1].id = i + 1;
        tanks[i + 1].A = initial_coords[i].first;
        tanks[i + 1].B = initial_coords[i].second;
        tanks[i + 1].is_hit = false;
    }
    for (int id : hit_tank_ids) {
        tanks[id].is_hit = true;
    }

    adj.assign(N + 1, vector<int>());
    parent_adj.assign(N + 1, vector<int>());

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j) continue;

            if (contains(tanks[i], tanks[j])) {
                bool direct_containment = true;
                for (int k = 1; k <= N; ++k) {
                    if (k == i || k == j) continue;
                    if (contains(tanks[i], tanks[k]) && contains(tanks[k], tanks[j])) {
                        direct_containment = false;
                        break;
                    }
                }
                if (direct_containment) {
                    adj[i].push_back(j);
                    parent_adj[j].push_back(i);
                }
            }
        }
    }

    vector<int> root_tanks;
    for (int i = 1; i <= N; ++i) {
        if (parent_adj[i].empty()) {
            root_tanks.push_back(i);
        }
    }

    vector<int> num_hit_tanks_in_subtree(N + 1, 0);
    function<void(int)> calculateHitCounts = [&](int u) {
        if (tanks[u].is_hit) {
            num_hit_tanks_in_subtree[u] = 1;
        }
        for (int v : adj[u]) {
            calculateHitCounts(v);
            num_hit_tanks_in_subtree[u] += num_hit_tanks_in_subtree[v];
        }
    };

    for (int root : root_tanks) {
        calculateNestedCounts(root, tanks, adj);
        calculateHitCounts(root);
    }

    map<int, int> hit_tank_id_to_idx;
    for (int i = 0; i < M; ++i) {
        hit_tank_id_to_idx[hit_tank_ids[i]] = i;
    }

    vector<long long> covered_masks(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        vector<bool> temp_covered_hits(N + 1, false);
        getCoveredHitTanks(i, tanks, adj, temp_covered_hits);
        for (int hit_id : hit_tank_ids) {
            if (temp_covered_hits[hit_id]) {
                covered_masks[i] |= (1LL << hit_tank_id_to_idx[hit_id]);
            }
        }
    }

    vector<bool> is_covered_hit(N + 1, false);
    vector<int> picked_tanks_result;
    int current_total_unrelated = 0;
    int current_picked_count = 0;

    int num_covered_global = 0;
    for (int hit_id : hit_tank_ids) {
        if (tanks[hit_id].is_hit) {
            num_covered_global++;
        }
    }

    while (num_covered_global < M) {
        int best_candidate_id = -1;
        int max_newly_covered = -1;
        int min_unrelated_cost_for_best = -1;

        for (int i = 1; i <= N; ++i) {
            bool covers_any_uncovered = false;
            long long temp_mask = covered_masks[i];

            for (int k = 0; k < M; ++k) {
                if ((temp_mask & (1LL << k)) && !is_covered_hit[hit_tank_ids[k]]) {
                    covers_any_uncovered = true;
                    break;
                }
            }

            if (!covers_any_uncovered) continue;

            int current_newly_covered = 0;
            for (int k = 0; k < M; ++k) {
                if ((temp_mask & (1LL << k)) && !is_covered_hit[hit_tank_ids[k]]) {
                    current_newly_covered++;
                }
            }

            int current_unrelated_cost = tanks[i].total_nested_count - num_hit_tanks_in_subtree[i];
            if (current_unrelated_cost < 0) current_unrelated_cost = 0;

            if (current_newly_covered > max_newly_covered) {
                max_newly_covered = current_newly_covered;
                best_candidate_id = i;
                min_unrelated_cost_for_best = current_unrelated_cost;
            } else if (current_newly_covered == max_newly_covered) {
                if (current_unrelated_cost < min_unrelated_cost_for_best) {
                    best_candidate_id = i;
                    min_unrelated_cost_for_best = current_unrelated_cost;
                } else if (current_unrelated_cost == min_unrelated_cost_for_best) {
                    if (best_candidate_id == -1 || tanks[i].id < tanks[best_candidate_id].id) {
                       best_candidate_id = i;
                       min_unrelated_cost_for_best = current_unrelated_cost;
                    }
                }
            }
        }

        if (best_candidate_id == -1) {
            break;
        }

        picked_tanks_result.push_back(tanks[best_candidate_id].id);
        current_picked_count++;
        current_total_unrelated += min_unrelated_cost_for_best;

        long long chosen_mask = covered_masks[best_candidate_id];
        for (int k = 0; k < M; ++k) {
            if ((chosen_mask & (1LL << k)) && !is_covered_hit[hit_tank_ids[k]]) {
                is_covered_hit[hit_tank_ids[k]] = true;
                num_covered_global++;
            }
        }
    }

    sort(picked_tanks_result.begin(), picked_tanks_result.end());

    cout << current_picked_count << endl;
    for (int i = 0; i < picked_tanks_result.size(); ++i) {
        cout << picked_tanks_result[i] << (i == picked_tanks_result.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}