Submission #755275

#	Time	Username	Problem	Language	Result	Execution time	Memory
755275		Lucpp	Council (JOI23_council)	C++17	100 / 100	900 ms	35168 KiB

council

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;

int same(int x, int y){
    return __builtin_popcount(x & y);
}

int n, m;

vector<pi> dp, sec;

void add(int msk, int val){
    if(val == -1) return;
    int s = same(msk, val);
    if(s > dp[msk].first){
        sec[msk] = dp[msk];
        dp[msk] = {s, val};
    }
    else{
        if(dp[msk].second == val || sec[msk].second == val) return;
        if(s > sec[msk].first) sec[msk] = {s, val};
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vector<int> a(n), c(n), cnt(1<<m);
    vector<int> total(m);
    dp.assign(1<<m, {-1, -1});
    sec.assign(1<<m, {-1, -1});
    for(int i = 0; i < n; i++){
        int x = 0, y;
        for(int j = 0; j < m; j++){
            cin >> y;
            x += y*(1<<j);
            total[j] += y;
        }
        a[i] = x;
        c[i] = (~x)&((1<<m)-1);
        dp[c[i]] = {same(c[i], c[i]), c[i]};
        cnt[c[i]]++;
    }
    for(int msk = (1<<m)-1; msk >= 0; msk--){
        for(int i = 0; i < m; i++){
            if(msk & (1<<i)){
                add(msk ^ (1<<i), dp[msk].second);
                add(msk ^ (1<<i), sec[msk].second);
            }
        }
    }
    for(int msk = 0; msk < (1<<m); msk++){
        for(int i = 0; i < m; i++){
            if(msk & (1<<i)){
                add(msk, dp[msk ^ (1<<i)].second);
                add(msk, sec[msk ^ (1<<i)].second);
            }
        }
    }
    for(int i : a){
        int ans = 0;
        int crit = 0;
        for(int j = 0; j < m; j++){
            int votes = total[j];
            if(i & (1<<j)) votes--;
            if(votes > n/2){
                ans++;
            }
            if(votes == n/2){
                crit |= (1<<j);
            }
        }
        int x = dp[crit].second;
        if(x == -1 || (((~i)&((1<<m)-1)) == x && cnt[x] == 1)) x = sec[crit].second;
        if(x != -1) ans += same(x, crit);
        cout << ans << "\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