Submission #891880

#	Time	Username	Problem	Language	Result	Execution time	Memory
891880		alexander707070	Council (JOI23_council)	C++14	41 / 100	4022 ms	353636 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;

sol ff2(int mask){
    sol res={0,0,0,0};
   
    for(int i=1;i<=n;i++){
        if((a[i]&mask)==0 and res.t1==0){
            res.ans1=__builtin_popcount(mask);
            res.t1=i;
        }else if((a[i]&mask)==0 and res.t2==0){
            res.ans2=__builtin_popcount(mask);
            res.t2=i;
        }
    }

    return res;
}

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

sol ff(int n,int mask){
    if(n==-1)return ff2(mask);

    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];
        }
    }

    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:50: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]
   50 |         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: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22