Submission #1308367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308367		duongquanghai08	Council (JOI23_council)	C++20	100 / 100	1052 ms	11836 KiB

council

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 5;
int a[N], b[N], cnt[N], n, k;
pii dp[(1 << 20)];

pii maximize(int mask, pii A, pii B) {
    int cand[4] = {A.fi, A.se, B.fi, B.se};
    int u[4], sz = 0;
    for(int i = 0; i < 4; i++) {
        if(!cand[i]) continue;
        bool exists = false;
        for(int j = 0; j < sz; j++) if(u[j] == cand[i]) exists = true;
        if(!exists) u[sz++] = cand[i];
    }
    
    if(sz == 0) return {0, 0};
    if(sz == 1) return {u[0], 0};

    int best = -1, max_v = -1;
    for(int i = 0; i < sz; i++) {
        int val = __builtin_popcount(b[u[i]] & mask);
        if(val > max_v) {
            max_v = val;
            best = u[i];
        }
    }
    
    int second = 0, max_v2 = -1;
    for(int i = 0; i < sz; i++) {
        if(u[i] == best) continue;
        int val = __builtin_popcount(b[u[i]] & mask);
        if(val > max_v2) {
            max_v2 = val;
            second = u[i];
        }
    }
    return {best, second};
}

void Solve() {
    cin >> n >> k;
    a[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < k; j++) {
            int x; cin >> x;
            cnt[j] += x;
            if(x) a[i] += (1 << j);
            else b[i] += (1 << j);
        }
        dp[b[i]] = maximize(b[i], dp[b[i]], {i, 0});
    }
    for(int mask = 1; mask < (1 << k); mask++) {
        for(int i = 0; i < k; i++) {
            if((mask >> i) & 1) dp[mask] = maximize(mask, dp[mask], dp[mask ^ (1 << i)]);
        }
    }
    for(int mask = (1 << k) - 1; mask > 0; mask--) {
        for(int i = 0; i < k; i++) {
            if(!((mask >> i) & 1)) dp[mask] = maximize(mask, dp[mask], dp[mask ^ (1 << i)]);
        }
    }
    int limit = n / 2;
    for(int i = 1; i <= n; i++) {
        int ans = 0, mask = 0;
        for(int j = 0; j < k; j++) {
            int bit = (a[i] >> j) & 1;
            if(cnt[j] - bit == limit) mask += (1 << j);
            if(cnt[j] - bit > limit) ans++;
        }
        if(dp[mask].fi == i) cout << ans + __builtin_popcount(mask & b[dp[mask].se]) << '\n';
        else cout << ans + __builtin_popcount(mask & b[dp[mask].fi]) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}

• 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