Submission #985499

#	Time	Username	Problem	Language	Result	Execution time	Memory
985499		vjudge2	Council (JOI23_council)	C++17	78 / 100	4051 ms	80772 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) {
    vector<pair<int, int>> u;
    set<int> occ;
    for (auto& x : a) if (x.first != -1) u.push_back(x);
    for (auto& y : b) if (y.first != -1) u.push_back(y);
    sort(u.begin(), u.end(), [] (pair<int, int> x, pair<int, int> y) {
        return x.first > y.first;
    });
    a.clear();
    for (int i = 0; i < u.size(); i++) {
        if (!occ.count(u[i].second) && u[i].first != -1) {
            a.push_back(u[i]);
            occ.insert(u[i].second);
        }
    }
    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';
    }
}

Compilation message (stderr)

council.cpp: In function 'void update(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
council.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

• 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: 0 / 22