Submission #924570

#TimeUsernameProblemLanguageResultExecution timeMemory
924570ttamxCouncil (JOI23_council)C++14
100 / 100
457 ms18896 KiB
#pragma GCC optimize("O3, unroll-loops") #include<bits/stdc++.h> using namespace std; using pi = pair<int,int>; using ppi = pair<pi,pi>; const int N=3e5+5; const int M=25; const int K=(1<<20)+5; int n,m; int a[N],cnt[M]; ppi dp[K]; void upd(ppi &x,pi v){ if(v.second==x.first.second)return void(x.first=min(x.first,v)); x.second=min(x.second,v); if(x.first>x.second)swap(x.first,x.second); } void upd(ppi &x,ppi y){ upd(x,y.first); upd(x,y.second); } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for(int i=1;i<=n;i++){ for(int j=0;j<m;j++){ int x; cin >> x; a[i]|=x<<j; cnt[j]+=x; } } for(int i=0;i<1<<m;i++)dp[i]=ppi(pi(m,0),pi(m,0)); for(int i=1;i<=n;i++)upd(dp[a[i]],pi(0,i)); for(int k=1;k<1<<m;k<<=1){ for(int i=0;i<1<<m;i+=k<<1){ for(int j=0;j<k;j++){ int u=i+j,v=i+j+k; auto du=dp[u],dv=dp[v]; dp[v].first.first++; dp[v].second.first++; upd(dp[u],dv); upd(dp[v],du); } } } for(int i=1;i<=n;i++){ int mask=0,ans=0; for(int j=0;j<m;j++){ int res=cnt[j]-(a[i]>>j&1); if(res==n/2)mask|=1<<j; if(res>=n/2)ans++; } cout << ans-(dp[mask].first.second!=i?dp[mask].first:dp[mask].second).first << "\n"; } }

Compilation message (stderr)

council.cpp:1:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops")
      |                                        ^
council.cpp:17:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   17 | void upd(ppi &x,pi v){
      |                     ^
council.cpp:23:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   23 | void upd(ppi &x,ppi y){
      |                      ^
council.cpp:28:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   28 | 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...