Submission #1213972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213972		k1r1t0	Council (JOI23_council)	C++20	100 / 100	741 ms	15824 KiB

council

#include <bits/stdc++.h>

using namespace std;

const int N = 310000;
const int M = 20;

int n, m, a[N], c[M], dp[1 << M][2];

bool comp(int msk, int x, int y) {
	if (x == 0) return false;
	if (y == 0) return true;
	int c1 = __builtin_popcount(msk & ~a[x]);
	int c2 = __builtin_popcount(msk & ~a[y]);
	return c1 > c2;
}

void upd(int msk, int k) {
	if (k == dp[msk][0] || k == dp[msk][1])
		return;
	if (comp(msk, k, dp[msk][1]))
		swap(dp[msk][1], k);
	if (comp(msk, dp[msk][1], dp[msk][0]))
		swap(dp[msk][1], dp[msk][0]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int t; cin >> t;
			c[j] += t;
			a[i] |= (t << j);
		}
		upd((1 << m) - 1 & ~a[i], i);
	}
	for (int i = 0; i < m; i++)
		for (int msk = 0; msk < (1 << m); msk++)
			if (msk & (1 << i)) {
				upd(msk ^ (1 << i), dp[msk][0]);
				upd(msk ^ (1 << i), dp[msk][1]);
			}
	for (int i = 0; i < m; i++)
		for (int msk = 0; msk < (1 << m); msk++)
			if (!(msk & (1 << i))) {
				upd(msk ^ (1 << i), dp[msk][0]);
				upd(msk ^ (1 << i), dp[msk][1]);
			}
	for (int i = 1; i <= n; i++) {
		int msk = 0, ans = 0;
		for (int j = 0; j < m; j++) {
			int t = c[j];
			if (a[i] & (1 << j))
				t--;
			if (t > n / 2)
				ans++;
			if (t == n / 2)
				msk |= (1 << j);
		}
		if (dp[msk][0] == i)
			ans += __builtin_popcount(msk & ~a[dp[msk][1]]);
		else
			ans += __builtin_popcount(msk & ~a[dp[msk][0]]);
		cout << ans << '\n';
	}
}

• 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