Submission #1086977

#TimeUsernameProblemLanguageResultExecution timeMemory
1086977BananabreadCouncil (JOI23_council)C++17
6 / 100
122 ms9188 KiB
#include<bits/stdc++.h> #define ll long long #define ntr "\n" #define mod (ll)(1e9+7) #define taskname "temp" #define frep freopen("06-02.inp","r",stdin); freopen(taskname".out","w",stdout); using namespace std; ll pref[100]; ll arr[300001]; ll ans[300001]; ll cnt[1<<17]; ll best[1<<17]; ll n,m; ll one,two,zero; ll super[1<<17]; bool ison(ll x,ll i){ return (x>>i)&1; } ll flip(ll x){ return ((1<<m)-1)&~x; } ll cntc=0; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //frep; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=0;j<m;j++){ ll x; cin>>x; pref[j]+=x; arr[i]+=(x<<j); } cnt[arr[i]]++; } for(int i=0;i<m;i++){ if(pref[i]>=n/2+2) two|=(1<<i); if(pref[i]==n/2+1) one|=(1<<i); if(pref[i]==n/2) zero|=(1<<i); } // if(n<=3000){ // for(int i=1;i<=n;i++){ // for(int j=i+1;j<=n;j++){ // ll cnt=0; // for(int u=0;u<m;u++){ // ll c=pref[u]-ison(arr[i],u)-ison(arr[j],u); // if(c>=n/2) cnt++; // } // ans[i]=max(ans[i],cnt); // ans[j]=max(ans[j],cnt); // } // } // for(int i=1;i<=n;i++){ // cout<<ans[i]<<ntr; // } // return 0; // } for(int i=0;i<(1<<m);i++){ if(!cnt[i]) continue; ll mask=flip(i); for (int nextmask = mask; nextmask ; nextmask=(nextmask-1)&mask){ super[nextmask]+=cnt[i]; } } cout<<ntr; for(int mask=0;mask<(1<<m);mask++){ if(!cnt[mask]) continue; cnt[mask]--; ll ONE=(two | ( one & flip(mask) )); ll ZERO=( one | ( zero & flip(mask) )); // cout<<ONE<<' '<<ZERO<<ntr; ll optmask=0; for(int i=0;i<m;i++){ if(ONE&(1<<i)) continue; if(ZERO&(1<<i)) optmask|=(1<<i); } // cout<<optmask<<ntr; for(int nextmask=optmask;nextmask;nextmask=(nextmask-1)&optmask){ if(super[nextmask]>(nextmask&mask==0)) best[mask]=max(best[mask],(ll)__builtin_popcount(ONE|(ZERO&nextmask))); } // cout<<ntr<<ntr; best[mask]=max(best[mask],(ll)__builtin_popcount(ONE)); cnt[mask]++; } for(int i=1;i<=n;i++){ cout<<best[arr[i]]<<ntr; } }

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:79:46: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   79 |             if(super[nextmask]>(nextmask&mask==0))
      |                                          ~~~~^~~
#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...