Submission #1086593

#TimeUsernameProblemLanguageResultExecution timeMemory
1086593BananabreadCouncil (JOI23_council)C++17
16 / 100
78 ms48980 KiB
#include<bits/stdc++.h> #define ll long long #define ntr "\n" #define mod (ll)(1e9+7) #define taskname "temp" #define frep freopen("03-01.inp","r",stdin); freopen(taskname".out","w",stdout); using namespace std; ll pref[300001]; ll arr[300001][20]; ll ans[300001]; ll cnt[1<<14]={}; ll best[1<<14]={}; ll n,m; ll one,two,zero; void sub2(){ 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]-arr[i][u]-arr[j][u]; if(c>n/2-1) cnt++; } ans[i]=max(ans[i],cnt); ans[j]=max(ans[j],cnt); } } for(int i=1;i<=n;i++){ cout<<ans[i]<<ntr; } } inline bool ison(ll x,ll bit){ return (x&(1<<bit))>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++){ cin>>arr[i][j]; pref[j]+=arr[i][j]; } } if(n<=3000){ sub2(); return 0; } 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); } for(int i=1;i<=n;i++){ ll mask=0; for(int j=0;j<m;j++){ mask+=(arr[i][j]<<j); } cnt[mask]++; } for(int m1=0;m1<(1<<m);m1++){ if(!cnt[m1]) continue; cnt[m1]--; for(int m2=m1;m2<(1<<m);m2++){ if(!cnt[m2]) continue; ll cnt=( two | (one & ~( m1 | m2 ) ) | ( zero & ~( m1 & m2 ) ) ); //cout<<m1<<' '<<m2<<ntr; //cout<<cnt<<ntr; best[m1]=max(best[m1],(ll)__builtin_popcount(cnt)); best[m2]=max(best[m2],(ll)__builtin_popcount(cnt)); } cnt[m1]++; } for(int i=1;i<=n;i++){ ll mask=0; for(int j=0;j<m;j++){ mask+=(arr[i][j]<<j); } cout<<best[mask]<<ntr; } }
#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...