#include <bits/stdc++.h>
#define int long long
struct Node
{
int first_max;
int ind1;
int second_max;
int ind2;
Node()
{
first_max = 0;
ind1 = -1;
second_max = 0;
ind2 = -1;
}
};
Node relax(Node now, std::pair<int, int> be)
{
if (now.ind1 == -1 && be.second != now.ind1)
{
now.first_max = be.first;
now.ind1 = be.second;
}
else if (now.first_max < be.first)
{
if (be.second != now.ind1)
{
now.second_max = now.first_max;
now.ind2 = now.ind1;
}
now.first_max = be.first;
now.ind1 = be.second;
}
else if (now.ind2 == -1 && be.second != now.ind1)
{
now.second_max = be.first;
now.ind2 = be.second;
}
else if (now.second_max < be.first && be.second != now.ind1)
{
now.second_max = be.first;
now.ind2 = be.second;
}
return now;
}
signed
main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<int> all(n);
std::vector<Node> dp((1 << m));
for (int i = 0; i < n; i++)
{
int now = 0;
for (int j = 0; j < m; j++)
{
int help;
std::cin >> help;
if (help == 1)
{
now |= (1 << j);
}
}
all[i] = now;
dp[now] = relax(dp[now], std::make_pair(m - __builtin_popcount(now), i));
}
for (int i = 0; i < (1 << m); i++)
{
for (int j = 0; j < m; j++)
{
if (!((i >> j) & 1))
{
int help = i;
help |= (1 << j);
Node need = dp[i];
need.first_max--;
need.second_max--;
dp[help] = relax(dp[help], std::make_pair(need.first_max, need.ind1));
dp[help] = relax(dp[help], std::make_pair(need.second_max, need.ind2));
}
}
}
for (int i = (1 << m) - 1; i >= 0; i--)
{
for (int j = 0; j < m; j++)
{
if ((i >> j) & 1)
{
int help = i;
help ^= (1 << j);
dp[help] = relax(dp[help], std::make_pair(dp[i].first_max, dp[i].ind1));
dp[help] = relax(dp[help], std::make_pair(dp[i].second_max, dp[i].ind2));
}
}
}
std::vector<int> type(m);
for (int i = 0; i < m; i++)
{
int cnt = 0;
for (int j = 0; j < n; j++)
{
if ((all[j] >> i) & 1)
{
cnt++;
}
else
{
cnt--;
}
}
if (cnt < -1)
{
type[i] = -2;
}
else if (cnt == -1)
{
type[i] = -1;
}
else if (cnt == 0)
{
type[i] = -1;
}
else if (cnt == 1 || cnt == 2)
{
type[i] = 0;
}
else
{
type[i] = 1;
}
// std::cout << i << ' ' << type[i] << std::endl;
}
std::vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int ind = (1 << m) - 1;
int cnt = 0;
for (int j = 0; j < m; j++)
{
if (type[j] == 1)
{
cnt++;
continue;
}
if ((all[i] >> j) & 1)
{
if (type[j] == 0)
{
ind ^= (1 << j);
}
}
else
{
if (type[j] == 0)
{
cnt++;
}
if (type[j] == -1)
{
ind ^= (1 << j);
}
}
}
// for (int j = 0; j < m; j++)
// {
// if ((ind >> j) & 1)
// {
// std::cout << "0";
// }
// else
// {
// std::cout << "1";
// }
// }
// std::cout << std::endl;
// std::cout << ind << ' ' << cnt << ' ' << dp[ind].first_max << std::endl;
if (dp[ind].ind1 == i)
{
ans[i] = cnt + dp[ind].second_max;
}
else
{
ans[i] = cnt + dp[ind].first_max;
}
}
for (int i = 0; i < n; i++)
{
std::cout << ans[i] << std::endl;
}
return 0;
}
# | 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... |