Submission #1176244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176244		mactoddlover	Council (JOI23_council)	C++17	100 / 100	769 ms	103436 KiB

council

#include<bits/stdc++.h>

#define pii pair<int,int>
#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
#ifdef LOCAL
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
#endif // LOCAL
}

signed main(){
    fastIO();

    int N, M; cin >> N >> M;

    vector<vector<int>> A(N, vector<int>(M, 0));
    vector<int> vote(M);
    vector<int> judge(N);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> A[i][j];
            vote[j] += A[i][j];
            judge[i] += A[i][j]*(1 << j);
        }
    }

    const int limit = N / 2;

    // submask take from inv_mask
    vector<pii> fake_dp(1 << M, pii(-1, -1));
    // mask match with inv_mask(judge) through submask
    vector<vector<pii>> dp((1 << M), vector<pii>(2, pii(-1, -1)));

    for(int i = 0; i < N; i++){
        int inv_mask = ((1 << M) - 1) ^ judge[i];
        if(fake_dp[inv_mask].fi == -1) fake_dp[inv_mask].fi = i;
        else if(fake_dp[inv_mask].se == -1) fake_dp[inv_mask].se = i;
    }

    for(int i = 0; i < M; i++){
        for(int mask = (1 << M) - 1; mask >= 0; mask--){
            if(!(mask >> i & 1)){
                vector<int> used = {fake_dp[mask].fi, fake_dp[mask].se,
                                    fake_dp[mask ^ (1 << i)].fi, fake_dp[mask ^ (1 << i)].se};
                sort(rall(used));
                fake_dp[mask].fi = used[0];
                fake_dp[mask].se = used[1];
            }
        }
    }

    auto update = [&](int mask, pii e) -> void{
        //check if index already in mask
        if(dp[mask][0].se == e.se) maximize(dp[mask][0], e);
        else maximize(dp[mask][1], e);

        if(dp[mask][0] < dp[mask][1]) swap(dp[mask][0], dp[mask][1]);
    };

    for(int mask = 0; mask < (1 << M); mask++){
        if(fake_dp[mask].fi != -1) update(mask, pii(__builtin_popcount(mask), fake_dp[mask].fi));
        if(fake_dp[mask].se != -1) update(mask, pii(__builtin_popcount(mask), fake_dp[mask].se));
    }

    for(int i = 0; i < M; i++){
        for(int mask = 0; mask < (1 << M); mask++){
            if(mask >> i & 1){
                update(mask, dp[mask ^ (1 << i)][0]);
                update(mask, dp[mask ^ (1 << i)][1]);
            }
        }
    }

    for(int i = 0; i < N; i++){
        int mask = 0;
        int sure = 0;

        for(int j = 0; j < M; j++){
            int cur_vote = vote[j] - A[i][j];
            if(cur_vote < limit) continue;
            sure += (cur_vote > limit);
            mask += (cur_vote == limit)*(1 << j);
        }

        int clutch = (dp[mask][0].se == i) ? dp[mask][1].fi : dp[mask][0].fi;

        cout << sure + clutch << endl;
    }
}

/*
    What i learn:

    answer = sure + clutch --> we wanna maximize clutch

    clutch = bits(mask) - min(bits(mask & mask_vote[j])) (i != j)

    go with the logic:  1 0 -> 1
                        1 1 -> 0
    we simply inverse the second mask:
                        1 1 -> 1
                        1 0 -> 0
    now: answer = max(bits(mask & inverse[mask_vote[j]]))

    submask = mask & inverse[mask_vote[j]]

    --> dp sos to take from inv_mask and match with needed_mask
*/

• 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