#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V> void __print(const pair<T, V> &x) {
cerr << '{';
__print(x.first);
cerr << ", ";
__print(x.second);
cerr << '}';
}
template <typename T> void __print(const T &x) {
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? ", " : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) \
cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \
_print(x); \
cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
#include int long long
#define rrep(i,n) for(int i=1; i<=n; i++)
#define rep(i,n) for(int i=0; i<n; i++)
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define pb push_back
int popcnt(int x){
assert(x>=0);
return __builtin_popcount(x);
}
int N,M;
const int MAXN = 300100;
int x[MAXN];
int p[30];
int cnt[MAXN];
long long dp[22][3000000];
int comb[300][300];
void solve(){
comb[1][0] = 1;
comb[1][1] = 1;
for(int i=2; i<=22; i++){
for(int j=0; j<=i; j++){
comb[i][j] = comb[i-1][j]+(j!=0 ? comb[i-1][j-1] : 0);
}
}
cin >> N >> M;
int k = N/2;
const int MSK = (1<<M) - 1;
rep(i,N){
rep(j,M){
int a; cin >> a;
if(a==0) continue;
p[j] += a;
x[i] |= (1<<j);
}
x[i] = (~x[i])&MSK;
}
int zeros=0, ones=0, twos=0;
rep(j,M){
if(p[j]>=k+2) zeros |= (1<<j);
if(p[j]==k+1) ones |= (1<<j);
if(p[j]==k) twos |= (1<<j);
}
rep(i,N) cnt[x[i]]++;
for(int i=0; i<M; i++){
for(int j=0; j<=MSK; j++){
if( (j & (1<<i)) ==0) {
cnt[j] += cnt[j^(1<<i)];
}
}
}
for(int j=0; j<= MSK; j++) dp[popcnt(j)][j] = cnt[j];
for(int i=0; i<M; i++){
for(int j=0; j<=MSK; j++){
if(j&(1<<i)){
rep(k,M) dp[k][j] += dp[k][j^(1<<i)];
}
}
}
rep(i,N){
int tmp = (ones&(~x[i])) | (twos&(x[i]));
assert(tmp>=0 && tmp<=MSK);
// tmp maximize tmp | x[j];
int MM = 0;
bool flag = false;
long long sum = 0, first_big=0, id=0;
for(int k=M; k>0; k--){
if(!flag && dp[k][tmp]>0LL){
if(popcnt(tmp&x[i])!=k){
MM = k; break;
}
flag=true;
if(dp[k][tmp]>1){
MM = k; break;
}
first_big=k;
sum = 1;
id = 1;
continue;
}
if(flag){
assert(id<30 && first_big < 30);
sum = comb[first_big][id++];
if(dp[k][tmp]>sum){
MM = k; break;
}
}
}
cout << MM + popcnt(zeros|(ones&x[i])) << "\n";
}
}
int32_t main(void){
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int t =1; // cin >> t;
while(t--) solve();
}
Compilation message
council.cpp:50:10: error: #include expects "FILENAME" or <FILENAME>
50 | #include int long long
| ^~~
