Submission #889715

#	Time	Username	Problem	Language	Result	Execution time	Memory
889715		vjudge1	Council (JOI23_council)	C++17	41 / 100	4013 ms	56748 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);
			}
		//	cout << a[i][j] << ' ';
		}
		//cout << '\n';
		bits[i] = mask;
		index[mask].push_back(i);
	}
	vector<int> needs;
	for(int mask = 0; mask < (1<<m); mask++){
		if(index[mask].empty() == false) needs.push_back(mask);
	}
	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{
		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 bits : needs){
				if((index[bits][0] != i || index[bits].back() != i)){
					pair<int, int> gt1 = mnus(gt, bits);
					int s = __builtin_popcount(gt1.ff);
					s+= __builtin_popcount(gt1.ss);
					mx = max(mx, s);
				}
			}
			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: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22