Submission #1308431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308431		viobow	Council (JOI23_council)	C++20	100 / 100	443 ms	35256 KiB

council

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

// Định nghĩa các hằng số và macro
const int MAX_N = 300005;
const int MAX_M = 20;
const int LIMIT = (1 << MAX_M);

int n, m;
int vote[MAX_N]; // Lưu phiếu bầu gốc của từng người
int agree[MAX_M]; // Đếm tổng số phiếu thuận cho mỗi dự luật

// Struct để lưu Top 2 giá trị tốt nhất (tránh trường hợp trùng ID với chủ tịch)
struct Top2 {
    int v1, id1; // Best: giá trị và ID
    int v2, id2; // Second best: giá trị và ID

    Top2() {
        v1 = -1; id1 = -1;
        v2 = -1; id2 = -1;
    }

    // Hàm cập nhật một giá trị mới vào Top 2
    void update(int val, int id) {
        if (id == -1) return;
        // Nếu trùng ID với người đang giữ top 1, chỉ cập nhật giá trị nếu tốt hơn
        if (id == id1) {
            v1 = max(v1, val);
            return;
        }
        // Nếu trùng ID với người đang giữ top 2
        if (id == id2) {
            v2 = max(v2, val);
            // Sau khi cập nhật top 2, cần kiểm tra xem có đổi chỗ với top 1 không
            if (v2 > v1) {
                swap(v1, v2);
                swap(id1, id2);
            }
            return;
        }

        // Trường hợp ID mới hoàn toàn
        if (val > v1) {
            v2 = v1; id2 = id1;
            v1 = val; id1 = id;
        } else if (val > v2) {
            v2 = val; id2 = id;
        }
    }

    // Hàm trộn (merge) 2 struct Top2 (dùng cho DP)
    void merge(const Top2& other) {
        if (other.id1 != -1) update(other.v1, other.id1);
        if (other.id2 != -1) update(other.v2, other.id2);
    }
};

Top2 cover[LIMIT]; // Giai đoạn 1: Lưu ai bao phủ mask này
Top2 best[LIMIT];  // Giai đoạn 2: Lưu kết quả tối ưu cho truy vấn

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

    if (!(cin >> n >> m)) return 0;

    // 1. Nhập liệu
    for (int i = 1; i <= n; i++) {
        int mask = 0;
        for (int j = 0; j < m; j++) {
            int t; cin >> t;
            if (t == 1) mask |= (1 << j); // SỬA LỖI: Chỉ bật bit nếu t=1
            agree[j] += t;
        }
        vote[i] = mask;
    }

    // 2. Giai đoạn 1: SOS DP (Superset -> Subset)
    // Mục tiêu: cover[mask] lưu ID những người mà phiếu đảo (inv_vote) của họ LÀ SUPERSET của mask.
    // Tức là nếu mask có bit 1 ở đâu, thì người đó cũng có bit 1 ở đó (trong inv_vote).

    // Khởi tạo cơ bản
    for (int i = 1; i <= n; i++) {
        // Lấy phiếu đảo ngược: bit 1 nghĩa là người đó bầu 0 (hợp với danger)
        int inv = (~vote[i]) & ((1 << m) - 1);
        // Người i bao phủ chính xác cái inv mask của họ
        cover[inv].update(0, i); // Giá trị 0 ở đây không quan trọng, ta chỉ cần ID
    }

    // Lan truyền từ cha xuống con
    for (int i = 0; i < m; i++) {
        for (int mask = (1 << m) - 1; mask >= 0; mask--) {
            if ((mask >> i) & 1) {
                // Nếu mask có bit i bật (1...1), nó có thể nhận update từ mask cha (mask này cũng tồn tại trong tập con của người sở hữu mask)
                // Nhưng logic đúng ở đây là: Nếu tôi có mask "111", tôi cũng có "011".
                // Tức là người sở hữu "111" cũng sở hữu "011".
                // "111" (mask) -> "011" (sub).
                // Vậy sub nhận từ mask.
                int sub = mask ^ (1 << i);
                cover[sub].merge(cover[mask]);
            }
        }
    }

    // 3. Giai đoạn 2: SOS DP (Subset -> Superset)
    // Mục tiêu: best[mask] lưu max popcount của một mask HỢP LỆ (có trong cover) nằm bên trong mask truy vấn.

    // Khởi tạo cơ bản từ mảng cover
    for (int mask = 0; mask < (1 << m); mask++) {
        if (cover[mask].id1 != -1) {
            int p_count = __builtin_popcount(mask);
            best[mask].update(p_count, cover[mask].id1);
            if (cover[mask].id2 != -1) {
                best[mask].update(p_count, cover[mask].id2);
            }
        }
    }

    // Lan truyền từ con lên cha (để tìm max trong vùng)
    for (int i = 0; i < m; i++) {
        for (int mask = 0; mask < (1 << m); mask++) {
            if ((mask >> i) & 1) {
                int sub = mask ^ (1 << i);
                best[mask].merge(best[sub]);
            }
        }
    }

    // 4. Trả lời truy vấn
    int threshold = n / 2;
    for (int i = 1; i <= n; i++) {
        int safe_count = 0;
        int danger_mask = 0;

        for (int j = 0; j < m; j++) {
            // Tính số phiếu còn lại nếu bỏ phiếu của i đi
            int total_remain = agree[j] - ((vote[i] >> j) & 1);

            if (total_remain >= threshold + 1) {
                safe_count++; // Chắc chắn đậu
            } else if (total_remain == threshold) {
                danger_mask |= (1 << j); // Cần người khác bầu 0 vào vị trí này
            }
        }

        // Tìm người j tốt nhất trong danger_mask
        // Ta cần người mà inv_vote của họ giao với danger_mask có nhiều bit 1 nhất.
        // Mảng best[danger_mask] đã lưu chính xác điều này.

        int bonus = 0;
        Top2 res = best[danger_mask];

        if (res.id1 != -1) {
            if (res.id1 != i) {
                bonus = res.v1;
            } else {
                // Nếu người tốt nhất là chính mình, lấy người nhì
                if (res.id2 != -1) {
                    bonus = res.v2;
                } else {
                    bonus = 0;
                }
            }
        }

        cout << safe_count + bonus << "\n";
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22