제출 #1086821

#제출 시각아이디문제언어결과실행 시간메모리
1086821BananabreadCouncil (JOI23_council)C++17
40 / 100
532 ms13652 KiB
#include<bits/stdc++.h> #define ll int #define ntr "\n" #define mod (ll)(1e9+7) #define taskname "temp" #define frep freopen("03-05.inp","r",stdin); freopen(taskname".out","w",stdout); using namespace std; ll pref[20]; 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]; array<array<ll,2>,2> candi[1<<17]; void sub2(){ for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ ans[i]=max(ans[i],__builtin_popcount((two | (one & ~arr[i]) | ~arr[j] &(one | zero & ~arr[i])))); ans[j]=max(ans[j],__builtin_popcount((two | (one & ~arr[j]) | ~arr[i] &(one | zero & ~arr[j])))); } } for(int i=1;i<=n;i++){ cout<<ans[i]<<ntr; } } 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){ sub2(); return 0; } for(int i=0;i<(1<<m);i++){ if(!cnt[i]) continue; candi[i][0]={-1,-1}; candi[i][1]={-1,-1}; ll mask=(((1<<m)-1) & ~i); for (int nextmask = mask; nextmask ; nextmask=(nextmask-1)&mask){ super[nextmask]+=cnt[i]; } } for(int mask=0;mask<(1<<m);mask++){ for(int nextmask = mask; nextmask ; nextmask=(nextmask-1)&mask){ if(super[nextmask]>1){ if(__builtin_popcount(mask&nextmask)>=candi[mask][0][0]){ candi[mask][1]=candi[mask][0]; candi[mask][0]={__builtin_popcount(mask&nextmask),nextmask}; } else if(__builtin_popcount(mask&nextmask)>candi[mask][1][0]){ candi[mask][1][1]=max(candi[mask][1][1],nextmask); } } } } 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(auto i:candi[ZERO]){ if(i[1]==-1) break; // cout<<i[1]<<' '<<(ONE|(ZERO&i[1]))<<' '<<__builtin_popcount(ONE|(ZERO&i[1]))<<ntr; best[mask]=max(best[mask],__builtin_popcount(ONE|(ZERO&i[1]))); } //cout<<ntr<<ntr; best[mask]=max(best[mask],__builtin_popcount(ONE)); cnt[mask]++; } for(int i=1;i<=n;i++){ cout<<best[arr[i]]<<ntr; } }

컴파일 시 표준 에러 (stderr) 메시지

council.cpp: In function 'void sub2()':
council.cpp:20:96: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   20 |             ans[i]=max(ans[i],__builtin_popcount((two | (one & ~arr[i]) | ~arr[j] &(one | zero & ~arr[i]))));
      |                                                                                           ~~~~~^~~~~~~~~
council.cpp:20:83: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   20 |             ans[i]=max(ans[i],__builtin_popcount((two | (one & ~arr[i]) | ~arr[j] &(one | zero & ~arr[i]))));
      |                                                                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
council.cpp:21:96: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   21 |             ans[j]=max(ans[j],__builtin_popcount((two | (one & ~arr[j]) | ~arr[i] &(one | zero & ~arr[j]))));
      |                                                                                           ~~~~~^~~~~~~~~
council.cpp:21:83: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   21 |             ans[j]=max(ans[j],__builtin_popcount((two | (one & ~arr[j]) | ~arr[i] &(one | zero & ~arr[j]))));
      |                                                                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...