Submission #1086089

#TimeUsernameProblemLanguageResultExecution timeMemory
1086089BananabreadCouncil (JOI23_council)C++17
41 / 100
4014 ms27364 KiB
#include<bits/stdc++.h> #define ll int #define ntr "\n" #define mod (ll)(1e9+7) #define taskname "temp" #define frep freopen("03-06.inp","r",stdin); freopen(taskname".out","w",stdout); using namespace std; ll pref[300001]; ll arr[300001][21]; ll ans[300001]; ll cnt[1<<14]={}; ll best[1<<14]={}; ll maska[300001]; ll n,m; void sub2(){ for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ ll cnt=0; for(int u=1;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=1;j<=m;j++){ cin>>arr[i][j]; } } for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ pref[j]+=arr[i][j]; } //cout<<pref[j]<<' '; } //cout<<ntr; if(n<=3000){ sub2(); return 0; } for(int i=1;i<=n;i++){ ll mask=0; for(int j=0;j<m;j++){ mask+=arr[i][j+1]*(1<<j); } maska[i]=mask; cnt[mask]++; } for(int m1=0;m1<(1<<m);m1++){ if(!cnt[m1]) continue; cnt[m1]--; for(int m2=0;m2<(1<<m);m2++){ if(!cnt[m2]) continue; ll cnt=0; //cout<<m1<<' '<<m2<<ntr; for(int i=0;i<m;i++){ ll neg=ison(m1,i)+ison(m2,i); if(pref[i+1]-neg>n/2-1) cnt++; } //cout<<cnt<<ntr; best[m1]=max(best[m1],cnt); } cnt[m1]++; } for(int i=0;i<(1<<m);i++){ //cout<<best[i]<<ntr; } for(int i=1;i<=n;i++){ cout<<best[maska[i]]<<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...