Submission #922111

#	Time	Username	Problem	Language	Result	Execution time	Memory
922111		The_Samurai	Council (JOI23_council)	C++17	100 / 100	832 ms	57956 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;

int btc(int a) { return __builtin_popcount(a); }

void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n, vector(m, 0));
    vector<pair<int, int>> cnt(1 << m, make_pair(n, n));
    vector<int> bta(n + 1), have(m);
    auto upd = [&](int bt, int i) -> void {
        if (btc(bta[cnt[bt].first] & bt) < btc(bta[i] & bt)) cnt[bt] = make_pair(i, cnt[bt].first);
        else if (cnt[bt].first != i and btc(bta[cnt[bt].second] & bt) < btc(bta[i] & bt))
            cnt[bt].second = i;
    };
    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], 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);
        }
    }
    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;
//        cout << ans << ' ' << bta[i] << ' ' << __builtin_popcount(bta[i]) << endl;
        if (i == cnt[bt].first) ans += btc(bta[cnt[bt].second] & bt);
        else ans += btc(bta[cnt[bt].first] & bt);
        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: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22