Submission #1077836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077836		NeroZein	Council (JOI23_council)	C++17	100 / 100	1163 ms	72892 KiB

council

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n + 1, vector<int>(m));
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	vector<int> attainable(1 << m);
	vector<int> attainable2(1 << m);
	for (int i = 1; i <= n; ++i) {
		int mask = 0;
		for (int j = 0; j < m; ++j) {
			mask |= (1 << j) * a[i][j];
		}
		if (!attainable[mask]) {
			attainable[mask] = i;			
		} else {
			attainable2[mask] = i; 
		}
	}
	
	for (int j = 0; j < m; ++j) {
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (!(mask >> j & 1)) {
				continue; 
			}
			int cfrom = attainable[mask];
			int cfrom2 = attainable2[mask];
			
			if (cfrom == 0) {
				attainable[mask] = attainable[mask ^ (1 << j)];
				attainable2[mask] = attainable2[mask ^ (1 << j)];
			} else if (cfrom2 == 0) {
				attainable2[mask] = attainable[mask ^ (1 << j)];
			}
			assert(attainable[mask] == 0 || attainable[mask] != attainable2[mask]);
		}
	}
	vector<pair<int, int>> dp(1 << m);
	vector<pair<int, int>> dp2(1 << m);
	
	for (int mask = 0; mask < (1 << m); ++mask) {
		if (attainable[mask]) {
			dp[mask] = {mask, attainable[mask]};			
		} else {
			dp[mask] = {(1 << m) - 1, 0};
		}
		if (attainable2[mask]) {
			dp2[mask] = {mask, attainable2[mask]};			
		} else {
			dp2[mask] = {(1 << m) - 1, 0};
		}
	}
	
	for (int j = 0; j < m; ++j) {
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (mask >> j & 1) {
				continue; 
			}
			vector<pair<int, int>> vec = {dp[mask], dp2[mask], dp[mask | (1 << j)], dp2[mask | (1 << j)]};
			sort(vec.begin(), vec.end(), [&](pair<int, int>& x, pair<int, int>& y) {
				return __builtin_popcount(x.first) < __builtin_popcount(y.first); 
			});
			dp[mask] = vec[0];
			//~ cerr << "VEC: \n";
			for (int i = 0; i < 4; ++i) {
				//~ cerr << vec[i].first << ' ' << vec[i].second << endl; 
				if (vec[i].second != vec[0].second) {
					dp2[mask] = vec[i];
					break; 
				}
			}
			//~ cerr << endl; 
		}
	}
	
	vector<int> cnt(m); 
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			cnt[j] += a[i][j];
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			cnt[j] -= a[i][j];
		}
	
		int ans = 0; 
		int mask = 0; 
		for (int j = 0; j < m; ++j) {
			if (cnt[j] != n / 2) {
				mask |= (1 << j); 
			}
			if (cnt[j] > n / 2) {
				ans++; 
			}
		}
		//~ cerr << "mask: " << mask << ' ' << dp[mask].second << ' ' << dp2[mask].second << endl; 
		if (dp[mask].second != i) {
			ans += m - __builtin_popcount(dp[mask].first);
		} else if (dp2[mask].second != 0) {
			ans += m - __builtin_popcount(dp2[mask].first); 
		}
		cout << ans << '\n'; 
		for (int j = 0; j < m; ++j) {
			cnt[j] += a[i][j];
		}
	}
	
	return 0; 
}

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