#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 3e5 + 7;
int n, mask[mxN], m, dp[mxN][25], cnt[mxN], vote[mxN];
bool Check_bit(int u, int v)
{
return (u >> v) & 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < m; j++)
{
bool bit;
cin >> bit;
mask[i] += bit << j;
vote[j] += bit;
}
cnt[mask[i]]++;
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < (1 << m); j++)
{
if (Check_bit(j, i))
cnt[j ^ (1 << i)] += cnt[j];
}
}
for (int i = 0; i < (1 << m); i++)
dp[i][__builtin_popcount(i)] = cnt[i];
for (int num = 0; num <= m; num++)
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < (1 << m); j++)
{
if (!Check_bit(j, i))
dp[j ^ (1 << i)][num] += dp[j][num] - dp[j ^ (1 << i)][num + 1];
}
}
}
for (int i = 1; i <= n; i++)
{
int ans = 0, ed = 0;
for (int j = 0; j < m; j++)
{
if (vote[j] - Check_bit(mask[i], j) > n / 2)
ans++;
if (vote[j] - Check_bit(mask[i], j) == (n / 2))
ed += (1 << j);
}
for (int j = 0; j <= m; j++)
{
if (dp[ed][j] - (__builtin_popcount(ed & mask[i]) == j))
{
ans += __builtin_popcount(ed) - j;
break;
}
}
cout << ans << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |