Submission #889704

#	Time	Username	Problem	Language	Result	Execution time	Memory
889704		vjudge1	Council (JOI23_council)	C++17	16 / 100	4083 ms	25108 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);
	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;
	}
	/*
	for(int j = 0; j < m; j++){
		if(col & (1<<j)) cout << 1;
		else cout << 0;
	}
	cout << " <  ";
	for(int j = 0;j < m; j++){
		if(col1 & (1<<j)) cout << 1;
		else cout << 0;
	}
	cout << '\n';
	*/
	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;
	}
	
	
	for(int i = 0;i < n; i++) cout << ans[i] << '\n';
	return 0;
}

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