Submission #1016975

#TimeUsernameProblemLanguageResultExecution timeMemory
1016975alexddCouncil (JOI23_council)C++17
100 / 100
1014 ms22544 KiB
#include<bits/stdc++.h> using namespace std; int n,m; pair<int,int> dp[1100000];///dp[config] = numarul maxim de 0-uri care se afla pe pozitiile selectate in config int cnt1[25]; int v[300005]; pair<int,int> baga(pair<int,int> x, int newv, int config) { if(x.first==newv || x.second==newv) return x; if(__builtin_popcount(v[newv]&config) > __builtin_popcount(v[x.first]&config)) { return {newv,x.first}; } else if(__builtin_popcount(v[newv]&config) > __builtin_popcount(v[x.second]&config)) { return {x.first,newv}; } return x; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) { int config=0,a,cate=0; for(int j=0;j<m;j++) { cin>>a; if(a==0) config += (1<<j), cate++; else cnt1[j]++; } v[i]=config; dp[config] = baga(dp[config], i, config); } for(int config=1;config<(1<<m);config++) { for(int i=0;i<m;i++) { if(((1<<i)&config)) { dp[config] = baga(dp[config], dp[config-(1<<i)].first, config); dp[config] = baga(dp[config], dp[config-(1<<i)].second, config); } } } for(int config=(1<<m)-1;config>=0;config--) { for(int i=0;i<m;i++) { if(!((1<<i)&config)) { dp[config] = baga(dp[config], dp[config+(1<<i)].first, config); dp[config] = baga(dp[config], dp[config+(1<<i)].second, config); } } } for(int i=1;i<=n;i++) { int config=0,deja=0; for(int j=0;j<m;j++) { if(!((1<<j)&v[i])) cnt1[j]--; if(cnt1[j]>=n/2 && cnt1[j]-1<n/2) config += (1<<j); else if(cnt1[j]>=n/2) deja++; if(!((1<<j)&v[i])) cnt1[j]++; } if(dp[config].first==i) { cout<<deja+__builtin_popcount(config&v[dp[config].second])<<"\n"; } else { cout<<deja+__builtin_popcount(config&v[dp[config].first])<<"\n"; } } return 0; }
#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...