Submission #792596

#	Time	Username	Problem	Language	Result	Execution time	Memory
792596		winter0101	Council (JOI23_council)	C++14	100 / 100	660 ms	45136 KiB

council

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=3e5+9,maxm=20;
bool a[maxn][maxm+1];
int sum[maxm+1];
int mask[maxn];
pii f[1<<maxm];
pii add(pii p,int q){
if (q==0)return p;
if (p.fi==0){
    p.fi=q;
}
else if (p.fi!=0&&p.se==0){
    p.se=q;
}
return p;
}
pair<pii,pii> g[1<<maxm];
int nn(int x){
return __builtin_popcount(x);
}
int b[4];
pii add(pii &p, pii &q){
b[0]=p.fi,b[1]=p.se,b[2]=q.fi,b[3]=q.se;
sort(b,b+4);
vector<int>vcl;
vcl.pb(b[0]);
for1(i,1,3){
if (b[i]!=b[i-1])vcl.pb(b[i]);
}
if (sz(vcl)==0)return {0,0};
if (sz(vcl)==1)return {vcl[0],0};
return {vcl[0],vcl[1]};
}
#define piii pair<pii,pii>
pii c[4];
piii update(piii p, piii q){
c[0]=p.fi,c[1]=p.se,c[2]=q.fi,c[3]=q.se;
sort(c,c+4,greater<pii>());
if (c[0].fi==0)return {{0,0},{0,0}};
for1(i,1,3){
if (c[i].se!=c[0].se){
    return {c[0],c[i]};
}
}
return {c[0],{0,0}};
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m;
    cin>>n>>m;
    for1(i,1,n){
    for1(j,1,m){
    cin>>a[i][j];
    sum[j]+=a[i][j];
    if (!a[i][j]){
    mask[i]|=(1<<(j-1));
    //cout<<i<<" "<<j<<'\n';
    }
    }
    f[mask[i]]=add(f[mask[i]],i);
    }
    for1(j,0,m-1){
    for2(i,(1<<m)-1,0){
    if (i>>j&1){
        f[i-(1<<j)]=add(f[i-(1<<j)],f[i].fi);
        f[i-(1<<j)]=add(f[i-(1<<j)],f[i].se);
    }
    }
    }
    for1(i,0,(1<<m)-1){
    if (f[i].fi)g[i].fi={nn(i),f[i].fi};
    if (f[i].se)g[i].se={nn(i),f[i].se};
    }
    for1(i,0,(1<<m)-1){
    for1(j,0,m-1){
    if (i>>j&1){
    g[i]=update(g[i],g[i-(1<<j)]);
    }
    }
    }
    int limit=n/2;
    for1(i,1,n){
    int msk=0;
    int ans=0;
    int turn=0;
    for1(j,1,m){
    int nw=sum[j]-a[i][j];
    if (nw==limit){
        //can be 0
        msk+=(1<<(j-1));
        //cout<<j<<'\n';
        if (a[i][j]==0)turn++;
    }
    else if (nw>limit){
        ans++;
    }
    }
    //cout<<msk<<'\n';
    if (turn==g[msk].fi.fi)ans+=g[msk].se.fi;
    else ans+=g[msk].fi.fi;
    cout<<ans<<'\n';
    }
    //cout<<g[1890].fi<<" "<<g[1890].se;

}

• 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