Submission #985368

#	Time	Username	Problem	Language	Result	Execution time	Memory
985368		vjudge2	Council (JOI23_council)	C++17	62 / 100	4035 ms	57948 KiB

council

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

void update(vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
    vector<pair<int, int>> u;
    set<int> occ;
    // for (int i = 0; i < 2; i++) cout << a[i].first << ' ' << a[i].second << '\n';
    // for (int i = 0; i < 2; i++) cout << b[i].first << ' ' << b[i].second << '\n';
    for (int i = 0; i < 2; i++) {
        // if (!occ.count(a[i]) && a[i].first != -1) {
            u.push_back(a[i]);
            // occ.insert(a[i]);
        // }
        // if (!occ.count(b[i]) && b[i].first != -1) {
            u.push_back(b[i]);
            // occ.insert(b[i]);
        // }
    }
    sort(u.begin(), u.end(), [] (pair<int, int> x, pair<int, int> y) {
        return x.first > y.first;
    });
    vector<pair<int, int>> v;
    for (int i = 0; i < u.size(); i++) {
        if (!occ.count(u[i].second) && u[i].first != -1) {
            v.push_back(u[i]);
            occ.insert(u[i].second);
        }
    }
    while ((int) v.size() > 2) v.pop_back();
    while ((int) v.size() < 2) v.push_back({-1, -1});
    a = v;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);   
    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0), freq(m, 0), b(n, 0);
    vector<vector<pair<int, int>>> dp(1 << m, vector<pair<int, int>> (2, {-1, -1}));
    for (int i = 0; i < n; i++) {
        int x;
        for (int j = 0; j < m; j++) {
            cin >> x;
            a[i] += (x << j);
            b[i] += ((1 - x) << j);
            if (x) freq[j]++;
        }
        // bitset<6> bs(b[i]);
        // cout << bs.to_string() << '\n';
        vector<pair<int, int>> t = {{__builtin_popcount(b[i]), i}, {-1, -1}};
        update(dp[b[i]], t);
    }
//     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:23: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]
   23 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

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