This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll n, m;
ll A[300010][21];
ll a[300010];
ll siz;
ll dp1[2000010];
ll dp2[2000010][21];
ll cou[21];
ll b[21];
ll pas[21][21];
ll two, one, zero;
int main(void)
{
fastio
cin >> n >> m;
siz = (1LL << m) - 1;
for(ll i = 1 ; i <= n ; ++i)
{
for(ll j = 0 ; j < m ; ++j)
{
cin >> A[i][j];
cou[j] += A[i][j];
}
for(ll j = m - 1 ; j >= 0 ; --j)
{
a[i] <<= 1;
a[i] += A[i][j];
}
a[i] ^= siz;
dp1[a[i]]++;
}
for(ll i = 0 ; i < m ; ++i)
{
for(ll j = siz ; j >= 0 ; --j)
{
if(j & (1LL << i))
dp1[j ^ (1LL << i)] += dp1[j];
}
}
for(ll i = 0 ; i <= siz ; ++i)
dp2[i][__builtin_popcount(i)] += dp1[i];
for(ll i = 0 ; i <= m ; ++i)
{
for(ll j = 0 ; j < m ; ++j)
{
for(ll k = 0 ; k <= siz ; ++k)
{
if(k & (1LL << j))
dp2[k][i] += dp2[k ^ (1LL << j)][i];
}
}
}
pas[0][0] = 1;
for(ll i = 1 ; i <= 20 ; ++i)
{
pas[i][0] = pas[i][i] = 1;
for(ll j = 1 ; j < i ; ++j)
pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j];
}
for(ll i = 0 ; i < m ; ++i)
{
if(cou[i] >= n / 2 + 2)
two |= (1LL << i);
else if(cou[i] == n / 2 + 1)
one |= (1LL << i);
else if(cou[i] == n / 2)
zero |= (1LL << i);
}
for(ll i = 1 ; i <= n ; ++i)
{
ll ONE = two | (one & a[i]);
ll ZERO = (one & (~a[i])) | (zero & a[i]);
for(ll j = 0 ; j <= m ; ++j)
b[j] = dp2[ZERO][j];
ll gap = (a[i] & ZERO);
ll COU = __builtin_popcount(gap);
for(ll j = 0 ; j <= COU ; ++j)
b[j] -= pas[COU][j];
ll ans = 0;
for(ll j = 0 ; j <= m ; ++j)
{
if(b[j])
ans = max(ans, j);
}
cout << ans + __builtin_popcount(ONE) en;
}
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... |