Submission #985507

#	Time	Username	Problem	Language	Result	Execution time	Memory
985507		vjudge2	Council (JOI23_council)	C++17	100 / 100	978 ms	72840 KiB

council

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

inline int read() {
    int x=0;char ch=getchar_unlocked();
    while (!(ch >= '0' && ch <= '9')) ch=getchar_unlocked();
    while (ch >= '0' && ch <= '9'){x=x*10+ch-48;ch=getchar_unlocked();}
    return x;
}

void update(vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
    for (int i = b.size() - 1; i >= 0; i--) {
        pair<int, int> p = b[i];
        if (a.empty()) {
            a.push_back(p);
            continue;
        }
        if (a.size() == 1) {
            if (a[0].second != p.second) {
                a.push_back(p);
                if (a[0].first < a[1].first) swap(a[0], a[1]);
            }
            continue;
        }
        if (p.second == a[0].second && p.first > a[0].first) a[0].first = p.first;
        else if (p.second == a[0].second) continue;
        else if (p.second == a[1].second && p.first > a[1].first) a[1].first = p.first;
        else if (p.second != a[1].second) {
            if (p.first >= a[0].first) a[1] = a[0], a[0] = p;
            else if (p.first > a[1].first) a[1] = p;
        }
        if (a[0].first < a[1].first) swap(a[0], a[1]);
    }
    while ((int) a.size() > 2) a.pop_back();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);   
    int n = read(), m = read();
    vector<int> a(n, 0), freq(m, 0), b(n, 0);
    vector<vector<pair<int, int>>> dp(1 << m);
    for (int i = 0; i < n; i++) {
        int x;
        for (int j = 0; j < m; j++) {
            x = read();
            a[i] += (x << j);
            b[i] += ((1 - x) << j);
            if (x) freq[j]++;
        }
        // bitset<6> bs(b[i]);
        // cout << bs.to_string() << '\n';
        if (dp[b[i]].size() < 2) dp[b[i]].emplace_back(__builtin_popcount(b[i]), i);
    }
//     4 6
// 1 1 0 0 1 1
// 1 0 1 1 1 1
// 0 0 0 0 0 1
// 0 1 1 1 0 0
    // max(popcount(b[sth] & s))..
    for (int i = (1 << m) - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                int k = (i ^ (1 << j));
                vector<pair<int, int>> t = dp[i];
                for (auto& [x, y] : t) if (x != -1) x--;
                update(dp[k], t);
            }
        }
    }
    // for (int i = 0; i < (1 << m); i++) {
    //     bitset<6> bs(i);
    //     cout << bs.to_string() << '\n';
    //     cout << dp[i][0].first << ' ' << dp[i][1].first << '\n';
    // }
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                int k = (i ^ (1 << j));
                // if (i == 23) cout << "debug: " << dp[i][0].first << ' ' << dp[i][1].first << ' ' << dp[k][0].first << ' ' << dp[k][1].first << '\n';
                update(dp[i], dp[k]);
                // if (i == 23) cout << "debug: " << dp[i][0].first << ' ' << dp[i][1].first << '\n';
            }
        }
        // bitset<6> bs(i);
        // cout << bs.to_string() << '\n';
        // cout << dp[i][0].first << ' ' << dp[i][1].first << '\n';
    }
    for (int i = 0; i < n; i++) {
        int ans = 0, sub = 0;
        for (int j = 0; j < m; j++) {
            int cnter = freq[j];
            if (a[i] & (1 << j)) cnter--;
            if (cnter > n / 2) ans++;
            else if (cnter == n / 2) {
                sub += (1 << j);
                // cout << "crit: " << j << '\n';
            }
        }
        // cout << ans << '\n';
        // cout << dp[sub][0].first << ' ' << dp[sub][0].second << '\n';
        // cout << dp[sub][1].first << ' ' << dp[sub][1].second << '\n';
        if (i == dp[sub][0].second) cout << ans + dp[sub][1].first << '\n';
        else cout << ans + dp[sub][0].first << '\n';
    }
}

• 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