Submission #1167056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167056		thangdz2k7	Council (JOI23_council)	C++20	6 / 100	126 ms	25672 KiB

council

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
using pii = pair <int, int>;

#define Mask(i) (1 << (i))
#define Bit(x, i) ((x) >> (i) & 1)
#define bp(x) __builtin_popcount(x)

const int LG = 20;
const int N = Mask(LG);

int n, m, a[N][LG], state[N];
int ans[N], cnt_s[N], cnt_b[LG], f[N];
pii g[N];

pii operator + (const pii &A, const pii &B) {
    pii C;
    if (bp(A.fi) > bp(B.fi)){
        C.fi = A.fi;
        if (bp(A.se) > bp(B.fi)) C.se = A.se;
        else C.se = B.fi;
    }
    else {
        C.fi = B.fi;
        if (bp(A.fi) > bp(B.se)) C.se = A.fi;
        else C.se = B.se;
    }

    return C;
}

void process(){
    cin >> n >> m;
    int mx = Mask(m);

    for (int i = 0; i < n; ++ i){
        for (int j = 0; j < m; ++ j){
            cin >> a[i][j];
            if (a[i][j]) state[i] |= Mask(j), cnt_b[j] ++;
        }
        cnt_s[state[i]] ++;
        f[state[i] ^ (mx - 1)] ++;
    }

    for (int i = 0; i < m; ++ i){
        for (int mask = 0; mask < mx; ++ mask) if (!Bit(mask, i))
            f[mask] += f[mask ^ Mask(i)];
    }

    for (int mask = 0; mask < mx; ++ mask){
        if (!f[mask]) g[mask] = {0, 0};
        if (f[mask] == 1) g[mask] = {mask, 0};
        if (f[mask] > 1) g[mask] = {mask, mask};
    }

    for (int i = 0; i < m; ++ i)
        for (int mask = 0; mask < mx; ++ mask) if (Bit(mask, i))
            g[mask] = g[mask] + g[mask ^ Mask(i)];

    for (int mask1 = 0; mask1 < mx; ++ mask1) if (cnt_s[mask1]){

        int num = 0, fl = 0;
        for (int i = 0; i < m; ++ i){
            cnt_b[i] -= Bit(mask1, i);
            if (cnt_b[i] >= n / 2) num ++;
            if (cnt_b[i] == n / 2) fl |= Mask(i);
        }

        int z = g[fl].fi;
        if ((z & (mask1 ^ (mx - 1))) == z) z = g[fl].se;
        ans[mask1] = max(ans[mask1], num - bp(fl) + bp(z));

        for (int i = 0; i < m; ++ i)
            cnt_b[i] += Bit(mask1, i);
    }

    for (int i = 0; i < n; ++ i)
        cout << ans[state[i]] << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    process();
    return 0;
}

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