Submission #1077631

#TimeUsernameProblemLanguageResultExecution timeMemory
1077631vjudge1Council (JOI23_council)C++98
56 / 100
4075 ms21692 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vii; typedef pair<ll,ll> pii; #define F first #define S second #define all(v) v.begin(),v.end() #define pb push_back const ll M=2e6+10; const ll inf=2e18+10; const ll mod=1e9+7; ll n,m,a[M],cnt[M],cntb[40],ans[M]; int main() { ios_base::sync_with_stdio(0),cin.tie(0); cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { ll x; cin>>x; a[i]+=(x*(1<<j)); cntb[j]+=x; } for(int i=0;i<n;i++) { for(int j=a[i];j<(1<<m);j++,j|=a[i]) { cnt[j]++; } } for(int i=0;i<(1<<m);i++) ans[i]=-1; for(int i=0;i<n;i++) { ll res=0,x=0; for(int j=0;j<m;j++) { if(cntb[j]-bool(((1<<j)&a[i])>0)>n/2) res++; else if(cntb[j]-bool(((1<<j)&a[i])>0)==n/2) { x+=(1<<j); } } if(ans[x]>-1) { cout<<ans[x]<<'\n'; continue; } ll res1=0; for(int j=x;j>=0;j--) { if(j<0) break; j&=x; ll y=j+(((1<<m)-1)^x); if((a[i]&y)==a[i]) cnt[y]--; if(cnt[y]>0) res1=max(res1,(ll)__builtin_popcountll(x)-__builtin_popcountll(j)); if((a[i]&y)==a[i]) cnt[y]++; } ans[x]=res1+res; cout<<res1+res<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...