Submission #891885

#	Time	Username	Problem	Language	Result	Execution time	Memory
891885		alexander707070	Council (JOI23_council)	C++14	100 / 100	2750 ms	589420 KiB

council

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

struct sol{
    int ans1,t1;
    int ans2,t2;
}best;

int n,m,br[25],curr;
int a[MAXN],s[MAXN][25],res,ans;

pair<int,int> ind[1024*1024];

pair<int,int> dp2[25][1024*1024];
bool li2[25][1024*1024];

int inv(int x){
    return (1<<m)-1-x;
}

pair<int,int> ff2(int m,int mask){
    if(m==-1){
        return ind[inv(mask)];
    }

    if(li2[m][mask])return dp2[m][mask];
    li2[m][mask]=true;
   
    if(((1<<m)&mask)>0){
        dp2[m][mask]=ff2(m-1,mask);
    }else{
        pair<int,int> s=ff2(m-1,mask^(1<<m));
        dp2[m][mask]=ff2(m-1,mask);

        if(dp2[m][mask].first==0){
            dp2[m][mask]=s;
        }else{
            dp2[m][mask].second=max(dp2[m][mask].second,s.first);
        }        
    }

    return dp2[m][mask];
}

sol dp[25][1024*1024];
bool li[25][1024*1024];

sol ff(int n,int mask){
    if(n==-1){
        sol res={0,0,0,0};
        if(ff2(m-1,mask).first!=0){
            res.ans1=__builtin_popcount(mask);
            res.t1=ff2(m-1,mask).first;
        }

        if(ff2(m-1,mask).second!=0){
            res.ans2=__builtin_popcount(mask);
            res.t2=ff2(m-1,mask).second;
        }

        return res;
    }

    if(li[n][mask])return dp[n][mask];
    li[n][mask]=true;

    if((mask&(1<<n))==0){
        dp[n][mask]=ff(n-1,mask);
    }else{
        sol fr=ff(n-1,mask),sc=ff(n-1,mask^(1<<n));

        vector< pair<int,int> > w={{fr.ans1,fr.t1},{fr.ans2,fr.t2},{sc.ans1,sc.t1},{sc.ans2,sc.t2}};
        sort(w.begin(),w.end());
        reverse(w.begin(),w.end());

        dp[n][mask].ans1=w[0].first;
        dp[n][mask].t1=w[0].second;

        for(int i=1;i<w.size();i++){
            if(w[i].second==w[0].second)continue;  
            dp[n][mask].ans2=w[i].first; 
            dp[n][mask].t2=w[i].second;
            break;  
        }
    }

    return dp[n][mask];
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            cin>>s[i][f];
            a[i]*=2; a[i]+=s[i][f];

            br[f]+=s[i][f];
        }

        if(ind[a[i]].first==0)ind[a[i]].first=i;
        else ind[a[i]].second=i;
    }

    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++)br[f]-=s[i][f];
        
        curr=res=0;
        for(int f=1;f<=m;f++){
            curr*=2;
            if(br[f]==n/2)curr++;
            if(br[f]>n/2)res++;
        }

        best=ff(m-1,curr);

        if(best.t1!=i){
            ans=res+best.ans1;
        }else{
            ans=res+best.ans2;
        }

        cout<<ans<<"\n";

        for(int f=1;f<=m;f++)br[f]+=s[i][f];
    }

    return 0;
}

Compilation message (stderr)

council.cpp: In function 'sol ff(int, int)':
council.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=1;i<w.size();i++){
      |                     ~^~~~~~~~~

• 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