Submission #1146488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146488		KhoaDuy	Council (JOI23_council)	C++20	100 / 100	427 ms	41228 KiB

council

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void update(pair<pair<int,int>,pair<int,int>> &x,pair<int,int> y){
    if(y.first>x.first.first){
        if(y.second!=x.first.second){
            x.second=x.first;
        }
        x.first=y;
    }
    else if(y.first>x.second.first){
        if(y.second!=x.first.second){
            x.second=y;
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    int a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    vector<pair<pair<int,int>,pair<int,int>>> DP(1<<m);
    for(int mask=0;mask<(1<<m);mask++){
        DP[mask]={{-1,-1},{-1,-1}};
    }
    for(int i=0;i<n;i++){
        int mask=0;
        for(int j=0;j<m;j++){
            if(a[i][j]){
                mask^=(1<<j);
            }
        }
        update(DP[mask],{0,i});
    }
    for(int i=0;i<m;i++){
        for(int mask=0;mask<(1<<m);mask++){
            if(mask&(1<<i)){
                update(DP[mask],DP[mask^(1<<i)].first);
                update(DP[mask],DP[mask^(1<<i)].second);
            }
        }
    }
    for(int mask=0;mask<(1<<m);mask++){
        int rev=mask^((1<<m)-1);
        if(mask<rev){
            swap(DP[mask],DP[rev]);
        }
    }
    for(int mask=0;mask<(1<<m);mask++){
        int counter=__builtin_popcount(mask);
        if(DP[mask].first.first==0){
            DP[mask].first.first=counter;
        }
        if(DP[mask].second.first==0){
            DP[mask].second.first=counter;
        }
    }
    for(int mask=1;mask<(1<<m);mask++){
        for(int i=0;i<m;i++){
            if(mask&(1<<i)){
                update(DP[mask],DP[mask^(1<<i)].first);
                update(DP[mask],DP[mask^(1<<i)].second);
            }
        }
    }
    for(int mask=0;mask<(1<<m);mask++){
    }
    int dif[m];
    for(int j=0;j<m;j++){
        dif[j]=-1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==0){
                a[i][j]=-1;
            }
            dif[j]+=a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dif[j]-=a[i][j];
        }
        int ans=0;
        int mask=0;
        for(int j=0;j<m;j++){
            if(dif[j]>=1){
                ans++;
            }
            else if(dif[j]>=-1){
                mask^=(1<<j);
            }
        }
        if(DP[mask].first.second==i){
            ans+=DP[mask].second.first;
        }
        else{
            ans+=DP[mask].first.first;
        }
        cout << ans << endl;
        for(int j=0;j<m;j++){
            dif[j]+=a[i][j];
        }
    }
}

• 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