Submission #889985

#	Time	Username	Problem	Language	Result	Execution time	Memory
889985		vjudge1	Council (JOI23_council)	C++17	33 / 100	4054 ms	56704 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);
	}
	/*
	 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 mask = 0; mask < (1<<m); mask++){
				if(index[mask].empty() == false){
					int k = (gt.ff & mask);
					k = __builtin_popcount(k);
					if(index[mask][0] != i){
						mx = max(mx, __builtin_popcount(gt.ff) + __builtin_popcount(gt.ss) - k);
					}
					if(index[mask].back() != i){
						mx = max(mx, __builtin_popcount(gt.ff) + __builtin_popcount(gt.ss) - k);
					}
				}
			}
			/*
			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) - bit);	
				}
				if(mx_index[gt.ff][bit] != -1 && mx_index[gt.ff][bit] != i){
					mx = max(mx, __builtin_popcount(gt.ff) - bit);	
				}
			}
			* */
			ans[i]+= mx;
		}
	
	
	
	for(int i = 0;i < n; i++) cout << ans[i] << '\n';
	return 0;
}

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