Submission #1086795

#TimeUsernameProblemLanguageResultExecution timeMemory
1086795BananabreadCouncil (JOI23_council)C++17
56 / 100
4067 ms37940 KiB
#include<bits/stdc++.h> #define ll int #define ntr "\n" #define mod (ll)(1e9+7) #define taskname "temp" #define frep freopen("06-01.inp","r",stdin); freopen(taskname".out","w",stdout); #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC target("avx","sse2") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroint-loops") using namespace std; ll pref[300001]; ll arr[300001][20]; ll ans[300001]; ll cnt[1<<17]; ll best[1<<17]; ll n,m; ll one,two,zero; ll super[1<<17]; vector<ll> candi[1<<17]; 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; } } 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=1;i<=n;i++){ ll mask=0; for(int j=0;j<m;j++){ mask|=(arr[i][j]<<j); } cnt[mask]++; } 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=0;i<(1<<m);i++){ if(!cnt[i]) continue; ll mask=(((1<<m)-1) & ~i); for (int nextmask = mask; nextmask ; nextmask=(nextmask-1)&mask){ super[nextmask]+=cnt[i]; } } // for(int i=0;i<(1<<m);i++){ // cout<<super[i]<<' '; // } // cout<<ntr; for(int mask=0;mask<(1<<m);mask++){ if(!cnt[mask]) continue; cnt[mask]--; ll ONE=(two | ( one & ~mask )); ll ZERO=( one | ( zero & ~mask )); //cout<<ONE<<' '<<ZERO<<ntr; for(int nextmask=ZERO ; nextmask ; nextmask=(nextmask-1)&ZERO){ //cout<<nextmask<<' '; if(super[nextmask]>1){ best[mask]=max(best[mask],__builtin_popcount(ONE|(ZERO&nextmask))); } } //cout<<ntr; best[mask]=max(best[mask],__builtin_popcount(ONE)); cnt[mask]++; } 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; } }

Compilation message (stderr)

council.cpp:18:37: warning: bad option '-funroint-loops' to pragma 'optimize' [-Wpragmas]
   18 | #pragma GCC optimize("unroint-loops")
      |                                     ^
council.cpp:29:11: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   29 | void sub2(){
      |           ^
council.cpp:45:10: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   45 | int main(){
      |          ^
#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...