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>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
typedef pair<int,int> pii;
int ccs=-3;
inline void srt(pair<pii,pii>& a,pii b){
if(a.fs<b){
if(a.fs.sc==b.sc){
a.sc={0,ccs};
ccs--;
}
else{
a.sc=a.fs;
}
a.fs=b;
}
else{
if(a.sc<b && a.fs.sc!=b.sc){
a.sc=b;
}
}
}
inline void srt2(pair<pii,pii>& a,pair<pii,pii> b){
srt(a,b.fs);
srt(a,b.sc);
}
inline int get(int a,int b){
return (a>>b)&1;
}
signed main(){
AquA;
int n,m;
cin >> n >> m;
int bx=1<<m;
vector<int> v(n);
vector<pair<pii,pii> > dp(bx,{{0,-1},{0,-2}});
vector<int> cnt(m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int a;
cin >> a;
if(a){
cnt[j]++;
v[i]|=(1<<j);
}
}
int r=v[i]^(bx-1);
int z=__builtin_popcount(r);
srt(dp[r],{z,i});
}
for(int j=0;j<m;j++){
for(int i=bx-1;i>=0;i--){
if(!get(i,j)){
srt2(dp[i],dp[i^(1<<j)]);
}
}
}
for(int i=0;i<bx;i++){
if(dp[i].fs.sc>=0){
dp[i].fs.fs=__builtin_popcount(i);
}
if(dp[i].sc.sc>=0){
dp[i].sc.fs=__builtin_popcount(i);
}
}
for(int j=0;j<m;j++){
for(int i=0;i<bx;i++){
if(get(i,j)){
srt2(dp[i],dp[i^(1<<j)]);
}
}
}
for(int i=0;i<n;i++){
int ans=0,nw=0;
for(int j=0;j<m;j++){
if(get(v[i],j)){
cnt[j]--;
}
if(cnt[j]>=n/2 && cnt[j]-1<n/2){
nw|=(1<<j);
}
else{
if(cnt[j]>=n/2){
ans++;
}
}
}
if(dp[nw].fs.sc!=i){
cout << ans+dp[nw].fs.fs << '\n';
}
else{
cout << ans+dp[nw].sc.fs << '\n';
}
for(int j=0;j<m;j++){
if(get(v[i],j)){
cnt[j]++;
}
}
}
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... |