#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 3e5 + 69;
const int M = 21;
int a[N], cnt[M], n, m;
int t[M], k, gas, pr, suf, bt, b, ans, c, s, x;
vector<int> g[1030];
pair<pair<int, int>, pair<int, int>> bst[1030][1030];
int kurac[1030][1030];
signed main() {
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 0;j < m;j++) {
scanf("%d", &x);
if (x > 0) {
a[i] |= (1 << j);
cnt[j]++;
}
}
pr = (a[i] & ((1 << (m - k)) - 1));
suf = (a[i] >> (m - k));
g[pr].push_back(suf);
}
int k = (m + 1) / 2;
for (int i = 0;i < (1 << k);i++) {
for (int j = 0;j < (1 << (m - k));j++) {
kurac[i][j] = __builtin_popcount(i & j);
bst[i][j] = {{(1 << m) - 1, m + 1}, {(1 << m) - 1, m + 1}};
}
}
for (int j = 1;j <= n;j++) {
pr = (a[j] & ((1 << (m - k)) - 1));
gas = (a[j] >> (m - k));
for (int i = 0;i < (1 << k);i++) {
bt = kurac[gas][i];
if (bt < bst[pr][i].f.s) {
bst[pr][i].s = bst[pr][i].f;
bst[pr][i].f = {a[j], bt};
}
else if (bt < bst[pr][i].s.s)
bst[pr][i].s = {a[j], bt};
}
}
//sufix duzine k, prefix duzine m - k
for (int i = 1;i <= n;i++) {
b = ans = c = 0;
for (int j = 0;j < m;j++) {
gas = cnt[j] - ((a[i] & (1 << j)) > 0);
if (gas == (n >> 1)) {
b |= (1 << j);
c++;
}
else if (gas > (n >> 1))
ans++;
}
suf = (b >> (m - k)), s = c;
pr = (b & ((1 << (m - k)) - 1));
for (int j = 0;j < (1 << (m - k));j++) {
if (a[i] != bst[j][suf].f.f)
s = min(s, bst[j][suf].f.s + kurac[pr][j]);
else
s = min(s, bst[j][suf].s.s + kurac[pr][j]);
}
ans += c - s;
printf("%d\n", ans);
}
}
return 0;
}
Compilation message
council.cpp: In function 'int main()':
council.cpp:20:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
20 | scanf("%d", &x);
| ~^ ~~
| | |
| | long long int*
| int*
| %lld
council.cpp:71:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
71 | printf("%d\n", ans);
| ~^ ~~~
| | |
| int long long int
| %lld
council.cpp:20:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
65 ms |
8408 KB |
Output is correct |
3 |
Correct |
64 ms |
7708 KB |
Output is correct |
4 |
Correct |
47 ms |
8116 KB |
Output is correct |
5 |
Correct |
68 ms |
8312 KB |
Output is correct |
6 |
Correct |
47 ms |
8036 KB |
Output is correct |
7 |
Correct |
69 ms |
8196 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
65 ms |
8408 KB |
Output is correct |
3 |
Correct |
64 ms |
7708 KB |
Output is correct |
4 |
Correct |
47 ms |
8116 KB |
Output is correct |
5 |
Correct |
68 ms |
8312 KB |
Output is correct |
6 |
Correct |
47 ms |
8036 KB |
Output is correct |
7 |
Correct |
69 ms |
8196 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4528 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
242 ms |
13688 KB |
Output is correct |
21 |
Incorrect |
221 ms |
13904 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
65 ms |
8408 KB |
Output is correct |
3 |
Correct |
64 ms |
7708 KB |
Output is correct |
4 |
Correct |
47 ms |
8116 KB |
Output is correct |
5 |
Correct |
68 ms |
8312 KB |
Output is correct |
6 |
Correct |
47 ms |
8036 KB |
Output is correct |
7 |
Correct |
69 ms |
8196 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4528 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
242 ms |
13688 KB |
Output is correct |
21 |
Incorrect |
221 ms |
13904 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
65 ms |
8408 KB |
Output is correct |
3 |
Correct |
64 ms |
7708 KB |
Output is correct |
4 |
Correct |
47 ms |
8116 KB |
Output is correct |
5 |
Correct |
68 ms |
8312 KB |
Output is correct |
6 |
Correct |
47 ms |
8036 KB |
Output is correct |
7 |
Correct |
69 ms |
8196 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4528 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
242 ms |
13688 KB |
Output is correct |
21 |
Incorrect |
221 ms |
13904 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Runtime error |
3 ms |
4700 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |