Submission #805758

#TimeUsernameProblemLanguageResultExecution timeMemory
805758someoneCouncil (JOI23_council)C++14
100 / 100
629 ms22364 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; const int M = (1 << 20) + 42; int n, m, mask[M], occ[M], maxi[M][2]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) mask[i] = (1 << m) - 1; for(int i = 0; i < m; i++) occ[i] = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { int a; cin >> a; mask[i] -= a * (1 << j); occ[j] += a; } for(int i = 0; i < (1 << m); i++) { maxi[i][0] = M-2; maxi[i][1] = M-1; } for(int i = 0; i < n; i++) { if(maxi[mask[i]][0] >= M-2) maxi[mask[i]][0] = i; else maxi[mask[i]][1] = i; } for(int i = (1 << m)-1; i >= 0; i--) { for(int j = 0; j < m; j++) { if((i & (1 << j)) == 0) { if(maxi[i][0] >= M-2) { maxi[i][0] = maxi[i + (1 << j)][0]; maxi[i][1] = maxi[i + (1 << j)][1]; } else if(maxi[i][1] >= M-2 && maxi[i + (1 << j)][0] != maxi[i][0]) { maxi[i][1] = maxi[i + (1 << j)][0]; } } } } for(int i = 1; i < (1 << m); i++) for(int j = 0; j < m; j++) if(i & (1 << j)) { int id = i ^ (1 << j); for(int k = 0; k < 2; k++) { int val = __builtin_popcount(i & mask[maxi[id][k]]); if(maxi[id][k] != maxi[i][0] && maxi[id][k] != maxi[i][1]) { if(val > __builtin_popcount(i & mask[maxi[i][0]])) { maxi[i][1] = maxi[i][0]; maxi[i][0] = maxi[id][k]; } else if(val > __builtin_popcount(i & mask[maxi[i][1]])) { maxi[i][1] = maxi[id][k]; } } } } for(int i = 0; i < n; i++) { int bmask = 0, nb = 0; for(int j = 0; j < m; j++) { if((1 << j) & (mask[i] ^ (1 << j))) occ[j]--; if(occ[j] == n/2) bmask += (1 << j); if(occ[j] >= n/2) nb++; if((1 << j) & (mask[i] ^ (1 << j))) occ[j]++; } if(maxi[bmask][0] != i) { cout << nb - __builtin_popcount(bmask ^ (bmask & mask[maxi[bmask][0]])) << '\n'; } else { cout << nb - __builtin_popcount(bmask ^ (bmask & mask[maxi[bmask][1]])) << '\n'; } } }
#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...