# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 2e6 + 5, inf = 1e9;
int n, m, a[N], cnt[N], raod[N];
pii idx[N], dp[N][2];
void upd(int idx, int vl) {
if (!vl) return ;
int res = __builtin_popcount(idx & a[vl]);
if (res < dp[idx][0].f) {
dp[idx][1] = dp[idx][0];
dp[idx][0] = {res, vl};
} else if (res < dp[idx][1].f && vl != dp[idx][0].s) {
dp[idx][1] = {res, vl};
}
}
signed main() {
cin>>n>>m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
char ch; cin>>ch;
if (ch == '1') a[i] |= (1<<j),cnt[j]++;
}
}
for (int i = 1; i <= n; i++) {
int op = a[i] ^ ((1<<m) - 1);
int ff = 0;
if (!idx[op].f) idx[op].f = i;
else idx[op].s = i;
}
for (int i = (1<<m) - 1; i >= 0; i--) {
if (idx[i].f && idx[i].s) continue;
for (int j = 0; j < m; j++) {
if ((1<<j)&i) continue;
if (!idx[i].f) {
if (idx[i ^ (1<<j)].f) idx[i].f = idx[i ^ (1<<j)].f;
} else if (!idx[i].s) {
if (idx[i ^ (1<<j)].f && idx[i ^ (1<<j)].f != idx[i].f) {
idx[i].s = idx[i ^ (1<<j)].f;
}
if (idx[i ^ (1<<j)].s && idx[i ^ (1<<j)].s != idx[i].f) {
idx[i].s = idx[i ^ (1<<j)].s;
}
}
}
}
for (int i = 0; i < (1<<m); i++) {
dp[i][0] = dp[i][1] = {inf, 0};
if (idx[i].f) upd(i, idx[i].f); if (idx[i].s) upd(i, idx[i].s); // tu 0 aqvs saerto
for (int j = 0; j < m; j++) {
if ((1<<j)&i) { // tu me-j aqvs saerto
upd(i, dp[i ^ (1<<j)][0].s);
upd(i, dp[i ^ (1<<j)][1].s);
}
}
}
for (int i = 1; i <= n; i++) {
int res = 0, mask = 0;
for (int j = 0; j < m; j++) {
if ((1<<j)&a[i]) cnt[j]--;
if (cnt[j] == n / 2) mask |= (1<<j);//, cout<<j<<" ";
if (cnt[j] >= n / 2) res++;
if ((1<<j)&a[i]) cnt[j]++;
}
//cout<<res<<"\n";
if (dp[mask][0].s != i) cout<<res - dp[mask][0].f<<"\n";
else cout<<res - dp[mask][1].f<<"\n";
}
}
Compilation message
council.cpp: In function 'int main()':
council.cpp:32:13: warning: unused variable 'ff' [-Wunused-variable]
32 | int ff = 0;
| ^~
council.cpp:55:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
55 | if (idx[i].f) upd(i, idx[i].f); if (idx[i].s) upd(i, idx[i].s); // tu 0 aqvs saerto
| ^~
council.cpp:55:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
55 | if (idx[i].f) upd(i, idx[i].f); if (idx[i].s) upd(i, idx[i].s); // tu 0 aqvs saerto
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
231 ms |
20720 KB |
Output is correct |
| 6 |
Correct |
232 ms |
16716 KB |
Output is correct |
| 7 |
Correct |
235 ms |
19476 KB |
Output is correct |
| 8 |
Correct |
247 ms |
19872 KB |
Output is correct |
| 9 |
Correct |
263 ms |
24488 KB |
Output is correct |
| 10 |
Correct |
238 ms |
18756 KB |
Output is correct |
| 11 |
Correct |
253 ms |
21068 KB |
Output is correct |
| 12 |
Correct |
262 ms |
24588 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
212 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
0 ms |
212 KB |
Output is correct |
| 36 |
Correct |
0 ms |
340 KB |
Output is correct |
| 37 |
Correct |
0 ms |
340 KB |
Output is correct |
| 38 |
Correct |
0 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
352 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
3 ms |
596 KB |
Output is correct |
| 42 |
Correct |
3 ms |
600 KB |
Output is correct |
| 43 |
Correct |
4 ms |
596 KB |
Output is correct |
| 44 |
Correct |
3 ms |
596 KB |
Output is correct |
| 45 |
Correct |
4 ms |
596 KB |
Output is correct |
| 46 |
Correct |
26 ms |
2752 KB |
Output is correct |
| 47 |
Correct |
26 ms |
2864 KB |
Output is correct |
| 48 |
Correct |
29 ms |
3048 KB |
Output is correct |
| 49 |
Correct |
27 ms |
2736 KB |
Output is correct |
| 50 |
Correct |
28 ms |
3412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
231 ms |
20720 KB |
Output is correct |
| 6 |
Correct |
232 ms |
16716 KB |
Output is correct |
| 7 |
Correct |
235 ms |
19476 KB |
Output is correct |
| 8 |
Correct |
247 ms |
19872 KB |
Output is correct |
| 9 |
Correct |
263 ms |
24488 KB |
Output is correct |
| 10 |
Correct |
238 ms |
18756 KB |
Output is correct |
| 11 |
Correct |
253 ms |
21068 KB |
Output is correct |
| 12 |
Correct |
262 ms |
24588 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
212 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
0 ms |
212 KB |
Output is correct |
| 36 |
Correct |
0 ms |
340 KB |
Output is correct |
| 37 |
Correct |
0 ms |
340 KB |
Output is correct |
| 38 |
Correct |
0 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
352 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
3 ms |
596 KB |
Output is correct |
| 42 |
Correct |
3 ms |
600 KB |
Output is correct |
| 43 |
Correct |
4 ms |
596 KB |
Output is correct |
| 44 |
Correct |
3 ms |
596 KB |
Output is correct |
| 45 |
Correct |
4 ms |
596 KB |
Output is correct |
| 46 |
Correct |
26 ms |
2752 KB |
Output is correct |
| 47 |
Correct |
26 ms |
2864 KB |
Output is correct |
| 48 |
Correct |
29 ms |
3048 KB |
Output is correct |
| 49 |
Correct |
27 ms |
2736 KB |
Output is correct |
| 50 |
Correct |
28 ms |
3412 KB |
Output is correct |
| 51 |
Correct |
229 ms |
16648 KB |
Output is correct |
| 52 |
Incorrect |
204 ms |
24832 KB |
Output isn't correct |
| 53 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
44 ms |
804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
44 ms |
804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
44 ms |
804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1996 KB |
Output is correct |
| 3 |
Incorrect |
44 ms |
804 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
231 ms |
20720 KB |
Output is correct |
| 6 |
Correct |
232 ms |
16716 KB |
Output is correct |
| 7 |
Correct |
235 ms |
19476 KB |
Output is correct |
| 8 |
Correct |
247 ms |
19872 KB |
Output is correct |
| 9 |
Correct |
263 ms |
24488 KB |
Output is correct |
| 10 |
Correct |
238 ms |
18756 KB |
Output is correct |
| 11 |
Correct |
253 ms |
21068 KB |
Output is correct |
| 12 |
Correct |
262 ms |
24588 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
0 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
212 KB |
Output is correct |
| 33 |
Correct |
0 ms |
212 KB |
Output is correct |
| 34 |
Correct |
0 ms |
212 KB |
Output is correct |
| 35 |
Correct |
0 ms |
212 KB |
Output is correct |
| 36 |
Correct |
0 ms |
340 KB |
Output is correct |
| 37 |
Correct |
0 ms |
340 KB |
Output is correct |
| 38 |
Correct |
0 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
352 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
3 ms |
596 KB |
Output is correct |
| 42 |
Correct |
3 ms |
600 KB |
Output is correct |
| 43 |
Correct |
4 ms |
596 KB |
Output is correct |
| 44 |
Correct |
3 ms |
596 KB |
Output is correct |
| 45 |
Correct |
4 ms |
596 KB |
Output is correct |
| 46 |
Correct |
26 ms |
2752 KB |
Output is correct |
| 47 |
Correct |
26 ms |
2864 KB |
Output is correct |
| 48 |
Correct |
29 ms |
3048 KB |
Output is correct |
| 49 |
Correct |
27 ms |
2736 KB |
Output is correct |
| 50 |
Correct |
28 ms |
3412 KB |
Output is correct |
| 51 |
Correct |
229 ms |
16648 KB |
Output is correct |
| 52 |
Incorrect |
204 ms |
24832 KB |
Output isn't correct |
| 53 |
Halted |
0 ms |
0 KB |
- |
