Submission #889996

#	Time	Username	Problem	Language	Result	Execution time	Memory
889996		vjudge1	Council (JOI23_council)	C++17	56 / 100	4066 ms	57036 KiB

council

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 3e5;
int ans[N+10];


vector< vector<int> > build(int n, int m, vector< vector<int> > &a){
	
	vector<int> cnt(m);
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			cnt[j]+= a[i][j];
		}
	}
	vector< vector<int> > res(n);
	
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			if(cnt[j] > (n / 2) + 1){
				ans[i]++;
			}
		}
	}
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			if(cnt[j] == n / 2){
				res[i].push_back(a[i][j]);
			}else if(cnt[j] ==  (n / 2) + 1){
				res[i].push_back(a[i][j]);
			}
		}
	}
	return res;
}



pair<int, int> mnus(pair<int ,int> A, int bits){
	int fin = A.ff - (A.ff & bits);
	int fin1 = A.ss;
	int k = (A.ss & bits);
	fin|= k;
	fin1-= k;
	return {fin, fin1};
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	vector< vector<int> > a(n, vector<int>(m));
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			cin >> a[i][j];
		}
	}
	a = build(n, m, a);
	n = a.size();
	m = a[0].size();
	vector<int> cnt(m);
	int col = 0, col1 = 0;
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			cnt[j]+= a[i][j];
		}
	}
	
	for(int j = 0;j < m; j++){
		if(cnt[j] == n / 2) col+= (1<<j);
		else col1+= (1<<j);
	}
	vector<int> bits(n);
	vector<int> index[(1<<m) + 10];
	for(int i = 0;i < n; i++){
		int mask = 0;
		for(int j = 0;j < m; j++){
			if(a[i][j]){
				mask+= (1<<j);
			}
		}
		bits[i] = mask;
		index[mask].push_back(i);
	}
	if(n <= 3000){
		for(int i = 0;i < n; i++){
			pair<int, int> gt = mnus(make_pair(col, col1), bits[i]);
			
			int mx = 0;
			/*
			for(int j = 0;j < m; j++){
				if(gt.ff & (1<<j)) cout << 1;
				else cout << 0;
			}
			cout << "   -> ";
			for(int j = 0;j < m; j++){
				if(gt.ss & (1<<j)) cout << 1;
				else cout << 0;
			}
			cout << '\n';
			* */
			for(int j = 0;j < n; j++){
				if(i == j) continue;
				pair<int, int> gt1 = mnus(gt, bits[j]);
				int s = __builtin_popcount(gt1.ff);
				s+= __builtin_popcount(gt1.ss);
				mx = max(mx, s);
			}
			ans[i]+= mx;
		}
	}else{
	 vector< vector<int> > mx_index(1<<m, vector<int>(22, -1));
	vector< vector<int> > mn_index(1<<m, vector<int>(22, -1));
	for(int bits = 0; bits < (1<<m); bits++){
		for(int mask = 0; mask < (1<<m); mask++){
			if(index[mask].empty() == false){
				int k = (bits & mask);
				k = __builtin_popcount(k);
				if(index[mask].size() >= 2){
					if(mx_index[bits][k] == -1) mx_index[bits][k] = index[mask][0];
					if(mn_index[bits][k] == -1) mn_index[bits][k] = index[mask].back();
				}else{
					if(mx_index[bits][k] == -1) mx_index[bits][k] = index[mask][0];
					else if(mn_index[bits][k] == -1) mn_index[bits][k] = index[mask][0];
				}
			}
		}
	}
	
		for(int i = 0;i < n; i++){
			pair<int, int> gt = mnus(make_pair(col, col1), bits[i]);
			int mx = 0;
			
			
			for(int bit = 0; bit < 22; bit++){
				if(mn_index[gt.ff][bit] != -1 && mn_index[gt.ff][bit] != i){
					mx = max(mx, __builtin_popcount(gt.ff) + __builtin_popcount(gt.ss) - bit);	
				}
				if(mx_index[gt.ff][bit] != -1 && mx_index[gt.ff][bit] != i){
					mx = max(mx, __builtin_popcount(gt.ff) + __builtin_popcount(gt.ss) - bit);	
				}
			}
			
			ans[i]+= mx;
		}
	
}
	
	for(int i = 0;i < n; i++) cout << ans[i] << '\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: 0 / 22
• Subtask 7: 0 / 22