Submission #1260344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260344		new_acc	Council (JOI23_council)	C++20	100 / 100	558 ms	18908 KiB

council

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e6+10;
const int M=1e5+10;
const int SS=1<<20;
const int INFi=2e9;
const ll INFl=1e18;
const int mod=1e9+7;
const int p=70032301;
int n,t[N],m,il[N];
pair<int,int> dp[N],kt[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int i2=0;i2<m;i2++){
            int a;
            cin>>a;
            t[i]+=(1<<i2)*a;
            if(a) il[i2]++;
        }
        t[i]=(1<<m)-1-t[i];
        if(dp[t[i]].fi==0) dp[t[i]].fi=__builtin_popcount(t[i]),kt[t[i]].fi=i;
        else dp[t[i]].se=__builtin_popcount(t[i]),kt[t[i]].se=i;
        t[i]=(1<<m)-1-t[i];
    }
    for(int i=(1<<m)-1;i>=0;i--){
        for(int i2=0;i2<m;i2++){
            if((i&(1<<i2))){
                int curr=i-(1<<i2);
                if(dp[i].fi-1>dp[curr].fi and kt[i].fi==kt[curr].fi) dp[curr].fi=dp[i].fi-1;
                if(dp[i].fi-1>dp[curr].fi and kt[i].fi!=kt[curr].fi){
                    swap(dp[curr].fi,dp[curr].se);
                    swap(kt[curr].fi,kt[curr].se);
                    dp[curr].fi=dp[i].fi-1;
                    kt[curr].fi=kt[i].fi;
                }else if(dp[i].fi-1>dp[curr].se and kt[curr].fi!=kt[i].fi) dp[curr].se=dp[i].fi-1,kt[curr].se=kt[i].fi;
                if(dp[i].se-1>dp[curr].se and kt[i].se!=kt[curr].fi) dp[curr].se=dp[i].se-1,kt[curr].se=kt[i].se;
            }
        }
    }
    for(int i=0;i<(1<<m);i++){
        for(int i2=0;i2<m;i2++){
            if(!(i&(1<<i2))){
                int curr=i+(1<<i2);
                if(dp[i].fi>dp[curr].fi and kt[i].fi==kt[curr].fi) dp[curr].fi=dp[i].fi;
                if(dp[i].fi>dp[curr].fi and kt[i].fi!=kt[curr].fi){
                    swap(dp[curr].fi,dp[curr].se);
                    swap(kt[curr].fi,kt[curr].se);
                    dp[curr].fi=dp[i].fi;
                    kt[curr].fi=kt[i].fi;
                }else if(dp[i].fi>dp[curr].se and kt[i].fi!=kt[curr].fi) dp[curr].se=dp[i].fi,kt[curr].se=kt[i].fi;
                if(dp[i].se>dp[curr].se and kt[i].se!=kt[curr].fi) dp[curr].se=dp[i].se,kt[curr].se=kt[i].se;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int i2=0;i2<m;i2++){
            if((1<<i2)&t[i]) il[i2]--;
        }
        int curr=0,xd=0;
        for(int i2=0;i2<m;i2++){
            if(il[i2]==n/2){
                curr+=(1<<i2);
            }else if(il[i2]>n/2) xd++;
        }
        int res=dp[curr].fi;
        if(kt[curr].fi==i) res=dp[curr].se;
        cout<<res+xd<<"\n";
        for(int i2=0;i2<m;i2++){
            if((1<<i2)&t[i]) il[i2]++;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) 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