Submission #1077788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077788		vjudge1	Council (JOI23_council)	C++17	6 / 100	341 ms	27404 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; 
		}
		//~ if (i == 3) {
			//~ cerr << "msk: " << mask << endl; 
		//~ }
	}
	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]};			
		}
		if (attainable2[mask]) {
			dp2[mask] = {mask, attainable2[mask]};			
		}
	}
	
	for (int j = 0; j < m; ++j) {
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (mask >> j & 1) {
				continue; 
			}
			if (dp[mask | (1 << j)].second && dp[mask | (1 << j)].second != dp[mask].second && (!dp[mask].second || __builtin_popcount(dp[mask | (1 << j)].first) < __builtin_popcount(dp[mask].first))) {
				swap(dp[mask], dp2[mask]);
				dp[mask] = dp[mask | (1 << j)];
				if (dp2[mask | (1 << j)].second && dp2[mask | (1 << j)].second != dp2[mask].second && (!dp2[mask].second || __builtin_popcount(dp2[mask | (1 << j)].first) < __builtin_popcount(dp2[mask].first))) {
					dp2[mask] = dp2[mask | (1 << j)];
				}
			} else if (dp[mask | (1 << j)].second && dp[mask | (1 << j)].second != dp2[mask].second && dp[mask | (1 << j)].second != dp[mask].second && (!dp2[mask].second || __builtin_popcount(dp[mask | (1 << j)].first) < __builtin_popcount(dp2[mask].first))) {
				dp2[mask] = dp[mask | (1 << j)];
			}
		}
	}
	
	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++; 
			}
		}
		if (dp[mask].second != i) {
			ans += m - __builtin_popcount(dp[mask].first);
		} else {
			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: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22