제출 #1279761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279761		denislav	Council (JOI23_council)	C++20	6 / 100	301 ms	25096 KiB

council

# include <iostream>
# include <vector>
# include <cassert>
using namespace std;
void chmax(pair<int,int>& x, pair<int,int> y) {x=max(x,y);}

const int MAX=3e5+11,MAXM=20;

int n,m;
bool s[MAX][MAXM];
int MASK[MAX];
int tot[MAXM];
pair<int,int> ids[(1<<MAXM)+11];
pair<pair<int,int>,pair<int,int>> dp[(1<<MAXM)+11];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<(1<<m);i++) ids[i]={-1,-1};
    for(int i=1;i<=n;i++)
    {
        int mask=0;
        for(int bit=0;bit<m;bit++)
        {
            cin>>s[i][bit];
            int b=s[i][bit];
            if(b==1) tot[bit]++;
            else tot[bit]--;

            if(b==0) mask|=(1<<bit);
        }

        if(ids[mask].first==-1) ids[mask].first=i;
        else if(ids[mask].second==-1) ids[mask].second=i;
        MASK[i]=mask;
    }

    for(int mask=(1<<m)-1;mask>=0;mask--)
    {
        for(int bit=0;bit<m;bit++)
        {
            if(((1<<bit)&(mask))>0)
            {
                int mask2=(mask^(1<<bit));

                int x=ids[mask].first;
                if(x!=-1)
                {
                     if(ids[mask2].first==-1) ids[mask2].first=x;
                     else if(ids[mask2].second==-1) ids[mask2].second=x;
                }
                x=ids[mask].second;
                if(x!=-1)
                {
                     if(ids[mask2].first==-1) ids[mask2].first=x;
                     else if(ids[mask2].second==-1) ids[mask2].second=x;
                }
            }
        }
    }

    //for(int i=0;i<m;i++) cout<<tot[i]<<" ";
    //cout<<"\n";

    for(int mask=0;mask<(1<<m);mask++) dp[mask]={{0,0},{0,0}};
    for(int mask=0;mask<(1<<m);mask++)
    {
        int bits=__builtin_popcount(mask);
        int x=ids[mask].first;
        if(x!=-1)
        {
            //if(x==dp[mask].first.second) dp[mask].first={bits,x};
            //else if(x==dp[mask].second.second)
            //{
              //  dp[mask].second={bits,x};
               // swap(dp[mask].first,dp[mask].second);
            //}
            //else
            //{
                dp[mask].second=dp[mask].first;
                dp[mask].first={bits,x};
            //}
        }
        x=ids[mask].second;
        if(x!=-1)
        {
            //if(x==dp[mask].first.second) dp[mask].first={bits,x};
            //else if(x==dp[mask].second.second)
            //{
               // dp[mask].second={bits,x};
                //swap(dp[mask].first,dp[mask].second);
            //}
            //else
            //{
                dp[mask].second=dp[mask].first;
                dp[mask].first={bits,x};
            //}
        }

        //cout<<mask<<":"<<"\n";
        //cout<<dp[mask].first.first<<" "<<dp[mask].first.second<<"\n";
        //cout<<dp[mask].second.first<<" "<<dp[mask].second.first<<"\n";

        for(int bit=0;bit<m;bit++)
        {
            int mask2=(mask|(1<<bit));
            if(mask==mask2) continue;
            pair<int,int> pa=dp[mask].first;
            if(pa.second==dp[mask2].first.second)
            {
                chmax(dp[mask2].first,pa);
            }
            else if(pa.second==dp[mask2].second.second)
            {
                chmax(dp[mask2].second,pa);
                if(dp[mask2].second>dp[mask2].first) swap(dp[mask2].first,dp[mask2].second);
            }
            else if(pa>=dp[mask2].first)
            {
                dp[mask2].second=dp[mask2].first;
                dp[mask2].first=pa;
            }
            else if(pa>=dp[mask2].second) dp[mask2].second=pa;

            pa=dp[mask].second;
            if(pa.second==dp[mask2].first.second)
            {
                chmax(dp[mask2].first,pa);
            }
            else if(pa.second==dp[mask2].second.second)
            {
                chmax(dp[mask2].second,pa);
                if(dp[mask2].second>dp[mask2].first) swap(dp[mask2].first,dp[mask2].second);
            }
            else if(pa>=dp[mask2].first)
            {
                dp[mask2].second=dp[mask2].first;
                dp[mask2].first=pa;
            }
            else if(pa>=dp[mask2].second) dp[mask2].second=pa;

        }
    }

    for(int i=1;i<=n;i++)
    {
        int ans=0,mask=0;
        for(int bit=0;bit<m;bit++)
        {
            int b=s[i][bit];
            if(tot[bit]>2) ans++;
            else if(tot[bit]<-1) ans+=0;
            else if(tot[bit]==-1)
            {
                if(b==0) mask+=(1<<bit);
            }
            else if(tot[bit]==0)
            {
                if(b==0) mask+=(1<<bit);
            }
            else if(tot[bit]==1)
            {
                if(b==1) mask+=(1<<bit);
                else ans++;
            }
            else if(tot[bit]==2)
            {
                if(b==1) mask+=(1<<bit);
                else ans++;
            }
        }

        if(dp[mask].first.second!=i) ans+=dp[mask].first.first;
        else ans+=dp[mask].second.first;

        /*
        int ans2=0;
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            int mask2=(mask&MASK[j]);
            ans2=max(ans2,__builtin_popcount(mask2));
        }
        ans+=ans2;
        */

        cout<<ans<<"\n";
    }

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22