Submission #1033330

#TimeUsernameProblemLanguageResultExecution timeMemory
1033330AndreyCouncil (JOI23_council)C++14
6 / 100
223 ms41116 KiB
#include<bits/stdc++.h> using namespace std; vector<pair<int,int>> bruh((1 << 20),{-1,-1}); vector<pair<int,int>> dp((1 << 20),{-1,-1}); vector<pair<int,int>> idk((1 << 20),{-1,-1}); vector<pair<int,int>> pos((1 << 20),{-1,-1}); void merge(int x, int c, int d) { if(c == -1) { return; } if(pos[x].first == c) { idk[x] = {max(d,idk[x].first),idk[x].second}; } else if(pos[x].second == c) { idk[x] = {idk[x].first,max(idk[x].second,d)}; } else { if(d > idk[x].first) { idk[x] = {d,idk[x].first}; pos[x] = {c,pos[x].first}; } else if(d > idk[x].second) { idk[x] = {idk[x].first,d}; pos[x] = {pos[x].first,c}; } } } pair<int,int> calc(pair<int,int> a, int b) { if(b == -1) { return a; } if(a.first == -1) { return {b,-1}; } else if(a.second == -1 && a.first != b) { return {a.first,b}; } return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,m,a; cin >> n >> m; vector<int> br(m); vector<int> haha(n); for(int i = 0; i < n; i++) { int c = 0; for(int j = 0; j < m; j++) { cin >> a; br[j]+=a; c+=a*(1 << j); } bruh[c] = calc(bruh[c],i); haha[i] = c; } for(int i = 0; i < (1 << m); i++) { dp[i] = bruh[i]; for(int j = 0; j < m; j++) { if((1 << j)&i) { dp[i] = calc(dp[i],dp[i-(1 << j)].first); dp[i] = calc(dp[i],dp[i-(1 << j)].second); } } } for(int i = (1 << m)-1; i >= 0; i--) { int br = 0; for(int j = 0; j < m; j++) { if(((1 << j)&i) == 0) { br++; } } if(dp[i].first != -1) { merge(i,dp[i].first,br); } if(dp[i].second != -1) { merge(i,dp[i].second,br); } for(int j = 0; j < m; j++) { if(((1 << j)&i) == 0) { merge(i,pos[i+(1 << j)].first,idk[i+(1 << j)].first); merge(i,pos[i+(1 << j)].second,idk[i+(1 << j)].second); } } } for(int i = 0; i < n; i++) { int x = 0,ans = 0; for(int j = 0; j < m; j++) { int c = br[j]; if((1 << j)&haha[i]) { c--; } if(c == n/2) { x+=(1 << j); } if(c > n/2) { ans++; } } x = (1 << m)-1-x; if(pos[x].first == i) { cout << ans+idk[x].second << "\n"; } else { cout << ans+idk[x].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...