Submission #890014

#	Time	Username	Problem	Language	Result	Execution time	Memory
890014		vjudge1	Council (JOI23_council)	C++17	40 / 100	4086 ms	271148 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;
}
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++){
			int msk = 0, c = 0;
			for(int j = 0;j < m; j++){
				if(bits[i] & (1<<j)){
					if(cnt[j] - 1==  n / 2){
						msk+= (1<<j);
						c++;
					}
				}else{
					if(cnt[j] == n / 2){
						msk+= (1<<j);
						c++;
					}else if(cnt[j] - 1==  n / 2){
						c++;
					}
				}
			}
			int mx = 0;
			for(int bit = 0; bit < 22; bit++){
				if(mn_index[msk][bit] != -1 && mn_index[msk][bit] != i){
					mx = max(mx, c - bit);	
					break;
				}
				if(mx_index[msk][bit] != -1 && mx_index[msk][bit] != i){
					mx = max(mx, c - bit);	
					break;
				}
			}
			
			ans[i]+= mx;
		}
	
	for(int i = 0;i < n; i++) cout << ans[i] << '\n';
	return 0;
}

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