Submission #921556

#	Time	Username	Problem	Language	Result	Execution time	Memory
921556		vjudge1	Council (JOI23_council)	C++17	16 / 100	4003 ms	19280 KiB

council

// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n, vector(m, 0));
    vector<pair<int, int>> cnt(1 << m);
    vector<int> bta(n), have(m);
    auto upd = [&](int bt, int v) -> void {
        if (cnt[bt].first < v) cnt[bt] = make_pair(v, cnt[bt].first);
        else cnt[bt].second = max(cnt[bt].second, v);
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (!a[i][j]) bta[i] |= 1 << j;
            have[j] += a[i][j];
        }
        upd(bta[i], __builtin_popcount(bta[i]));
    }
    for (int bt = (1 << m) - 1; bt >= 0; bt--) {
        for (int j = 0; j < m; j++) {
            if (bt & (1 << j)) continue;
            upd(bt, cnt[bt | (1 << j)].first);
            upd(bt, cnt[bt | (1 << j)].second);
        }
        cnt[bt].first = min(cnt[bt].first, __builtin_popcount(bt));
        cnt[bt].second = min(cnt[bt].second, __builtin_popcount(bt));
    }
    for (int bt = 0; bt < (1 << m); bt++) {
        for (int j = 0; j < m; j++) {
            if (bt & (1 << j)) continue;
            upd(bt | 1 << j, cnt[bt].first);
            upd(bt | 1 << j, cnt[bt].second);
        }
    }
    for (int i = 0; i < n; i++) {
        int ans = 0, bt = 0;
        for (int j = 0; j < m; j++) {
            have[j] -= a[i][j];
            if (have[j] != n / 2) ans += have[j] > n / 2;
            else bt |= 1 << j;
            have[j] += a[i][j];
        }
        int mx = 0;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            mx = max(mx, __builtin_popcount(bta[j] & bt));
        }
        ans += mx;
//        cout << ans << ' ' << bta[i] << ' ' << bt << ' ' << cnt[bt].first << ' ' << cnt[bt].second << endl;
//        if (__builtin_popcount(bta[i]) == cnt[bt].first) ans += cnt[bt].second;
//        else ans += cnt[bt].first;
        cout << ans << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--)  {
        solve();
        cout << '\n';
    }
}

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