Submission #754654

#	Time	Username	Problem	Language	Result	Execution time	Memory
754654		vjudge1	Council (JOI23_council)	C++17	100 / 100	522 ms	39248 KiB

council

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "tnc"  
typedef long long ll;
const ll INF=1e18;
const int maxn=3e5+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
pair<int,int>dp[1<<20];
pair<int,int>dp1[1<<20];
int n,m;
int ok[20];
int sum[maxn];
int num[20];
int ne[maxn];
int bang;
int larger;
int k1[1<<20];
int k2[1<<20];

  int so=0;
void printmask(int s){
	for(int i=0;i<so;i++){
		cout<<BIT(s,i);
	}
	cout<<"\n";
}
int convertmask(string s){
	int sum=0;
	for(int i=0;i<so;i++){
		if(s[i]=='1'){
			sum+=(1<<i);
		}
	}
	return sum;
}
signed main()
{
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    cin>>n>>m;
    int certain=0;
    for(int i=1;i<=n;i++){
    	for(int j=0;j<m;j++){
    		 int x;
    		 cin>>x;
    		 if(x==1){
    		 	sum[i]+=(1<<j);
    		 	num[j]++;
    		 }
    	}
    }
    for(int i=0;i<m;i++){
    	if(num[i]>=n/2+2){
    		certain++;
    	}
    	else if(num[i]>=n/2){
    		for(int j=1;j<=n;j++){
    			if((1<<i)&sum[j]){
    				ne[j]^=(1<<so);
    			}
    		}

    		if(num[i]==n/2){
    			bang+=(1<<so);
    		}
    		else{
    			larger+=(1<<so);
    		}
    		so++;
    	}
    }
    int N=(1<<so);
    for(int i=1;i<=n;i++){
    	int s=(N-1)^ne[i];
    	if(k1[s]==0){
    		k1[s]=i;
    	}
    	else if(k2[s]==0){
    		k2[s]=i;
    	}
    }

    for(int i=0;i<so;i++){
    	for(int j=N-1;j>=0;j--){
    		if(((1<<i)&j)==0){
    			if(k1[j]==0){
    				k1[j]=k1[j^(1<<i)];
    				k2[j]=k2[j^(1<<i)];
    			}
    			else if(k2[j]==0 && k1[j]!=k1[j^(1<<i)]){
    				k2[j]=k1[j^(1<<i)];
    			}
    		}
    	}
    }
    for(int i=0;i<N;i++){
    	int s=__builtin_popcount(i);
    	if(k1[i]){
    		dp[i]={s,k1[i]};
    	}
    	if(k2[i]){
    		dp1[i]={s,k2[i]};
    	}
    }
    for(int j=0;j<so;j++){
    	for(int i=0;i<N;i++){
    		if((1<<j)&i){
    			if(dp[i].fi<dp[i^(1<<j)].fi){

    				if(dp[i^(1<<j)].se!=dp[i].se)dp1[i]=dp[i];
    				dp[i]=dp[i^(1<<j)];
    				if(dp1[i^(1<<j)].fi>dp1[i].fi && dp1[i^(1<<j)].se!=dp1[i].se){
    					dp1[i]=dp1[i^(1<<j)];
    				}
    			}
    			else if(dp1[i].fi<dp[i^(1<<j)].fi && dp[i^(1<<j)].se!=dp[i].se){
    				dp1[i]=dp[i^(1<<j)];
    			}
    			else if(dp1[i].fi<dp1[i^(1<<j)].fi && dp1[i^(1<<j)].se!=dp[i].se){
    				dp1[i]=dp1[i^(1<<j)];

    			
    			}

    		}
    	}
	}
	for(int i=1;i<=n;i++){
		int k=bang^(bang&ne[i]);
		int alive=(larger^(larger&ne[i]));
		
		int k1=larger&ne[i];
		int neso=k^k1;
		alive=__builtin_popcount(alive);
		if(dp[neso].se==i){
			cout<<certain+alive+dp1[neso].fi<<"\n";
		}
		else{
			cout<<certain+alive+dp[neso].fi<<"\n";
		}
	}
	
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22