Submission #1063968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063968		MOUF_MAHMALAT	Council (JOI23_council)	C++14	100 / 100	512 ms	35172 KiB

council

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
const ll oo=3e5+9;
ll n,m,c[20];
bool b[20][oo];
pll dp[2][1<<20];
void solve()
{
    cin>>n>>m;
    for(ll i=0; i<(1<<m); i++)
        dp[0][i]=dp[1][i]= {-1,-1};
    for(ll i=0; i<n; i++)
    {
        ll mask=0;
        for(ll j=0; j<m; j++)
        {
            cin>>b[j][i];
            if(!b[j][i])
                mask|=(1<<j);
            c[j]+=b[j][i];
        }
        if(dp[0][mask].F== -1)
            dp[0][mask]= {1,i};
        else
            dp[1][mask]= {1,i};
    }
    for(ll j=m-1; j>=0; j--)
        for(ll i=(1<<m)-1; i>=0; i--)
        {
            if(!((1<<j)&i))
            {
                if(dp[0][i|(1<<j)].F!= -1)
                {
                    if(dp[0][i].F== -1)
                        dp[0][i]=dp[0][i|(1<<j)];
                    else if(dp[0][i].S!=dp[0][i|(1<<j)].S)
                        dp[1][i]=dp[0][i|(1<<j)];
                }
                if(dp[1][i|(1<<j)].F!= -1)
                {
                    if(dp[0][i].F== -1)
                        dp[0][i]=dp[1][i|(1<<j)];
                    else if(dp[0][i].S!=dp[1][i|(1<<j)].S)
                        dp[1][i]=dp[1][i|(1<<j)];
                }
            }
        }
    for(ll i=0; i<(1<<m); i++)
        for(ll j=0; j<2; j++)
            if(dp[j][i].F != -1)
            {
                ll x=__builtin_popcountll(i);
                dp[j][i].F=x;
            }
    for(ll j=0; j<m; j++)
        for(ll i=0; i<(1<<m); i++)
        {
            if(!((1<<j)&i))
                continue;
            pll a[4];
            a[0]=dp[0][i];
            a[1]=dp[1][i];
            a[2]=dp[0][i^(1<<j)];
            a[3]=dp[1][i^(1<<j)];
            sort(a,a+4,greater<pll>());
            dp[0][i]=a[0];
            dp[1][i]={-1,-1};
            for(ll k=1;k<4;k++)
                if(a[0].S!=a[k].S)
            {
                dp[1][i]=a[k];
                break;
            }
        }
//    for(ll i=0;i<(1<<m);i++)
//    {
//        cout<<dp[0][i].F<<" "<<dp[1][i].F<<"\n";
//        cout<<dp[0][i].S<<" ?? "<<dp[1][i].S<<"\n";
//    }
    for(ll i=0; i<n; i++)
    {
        ll mask=(1<<m)-1,ans=0;
        for(ll j=0; j<m; j++)
        {
            c[j]-=b[j][i];
            if(c[j]-1>=n/2)
                ans++,mask^=(1<<j);
            if(c[j]<n/2)
                mask^=(1<<j);
//            cout<<ans<<" ";
        }
//        cout<<"\n";
//        cout<<mask<<" "<<ans<<" "<<"!\n";
//        cout<<dp[0][mask].F<<" "<<dp[0][mask].S<<"\n";
//        cout<<dp[1][mask].F<<" "<<dp[1][mask].S<<"\n";
        if(dp[0][mask].S==i)
            cout<<ans+dp[1][mask].F<<"\n";
        else
            cout<<ans+dp[0][mask].F<<"\n";
        for(ll j=0;j<m;j++)
            c[j]+=b[j][i];
    }
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}
//3
//3
//3
//2
//3
//2
//2
//1
//3
//2
//2
//1
//2
//1
//1
//0

• 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