Submission #817291

#	Time	Username	Problem	Language	Result	Execution time	Memory
817291		happypotato	Council (JOI23_council)	C++17	100 / 100	1123 ms	26400 KiB

council

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 3e5 + 1;
int a[mxN];
int freq[20];
int n, m;
int dpf[(1 << 20)]; // 0 if no, pos if have 1, -1 if have 2+
pii dpb[(1 << 20)]; // {first to have 1, first to have 2+}
int popcount(int x) {
	return bitset<32>(x).count();
}
void init() {

}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			bool temp;
			cin >> temp;
			if (temp) {
				a[i] |= (1 << j);
				freq[j]++;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (dpf[a[i]] == 0) dpf[a[i]] = i;
		else dpf[a[i]] = -1;
	}
	for (int bit = 0; bit < m; bit++) {
		for (int msk = 0; msk < (1 << m); msk++) {
			if (msk & (1 << bit)) {
				int prev = (msk ^ (1 << bit));
				if (dpf[prev] == -1) dpf[msk] = -1;
				else if (dpf[prev] != 0) {
					if (dpf[msk] != 0) dpf[msk] = -1;
					else dpf[msk] = dpf[prev];
				}
			}
		}
	}

	for (int msk = 0; msk < (1 << m); msk++) {
		if (dpf[msk] == -1) dpb[msk] = {msk, msk};
		else if (dpf[msk] != 0) dpb[msk] = {msk, -1};
		else dpb[msk] = {-1, -1};
	}
	for (int bit = m - 1; bit >= 0; bit--) {
		for (int msk = 0; msk < (1 << m); msk++) {
			if (popcount(msk) != bit) continue;
			for (int i = 0; i < m; i++) {
				if (msk & (1 << i)) continue;
				int prev = (msk ^ (1 << i));

				if (dpb[prev].ff != -1) {
					// try to update 2
					if (dpf[dpb[prev].ff] != dpf[dpb[msk].ff]) {
						// take larger one
						if (popcount(dpb[prev].ff) > popcount(dpb[msk].ff)) {
							if (popcount(dpb[prev].ff) < popcount(dpb[msk].ss)) {
								dpb[msk].ss = dpb[prev].ff;
							}
						} else {
							if (popcount(dpb[msk].ff) < popcount(dpb[msk].ss)) {
								dpb[msk].ss = dpb[msk].ff;
							}
						}
					}
					// update only 1
					if (popcount(dpb[prev].ff) < popcount(dpb[msk].ff)) {
						dpb[msk].ff = dpb[prev].ff;
					}
				}

				if (dpb[prev].ss != -1) {
					if (popcount(dpb[prev].ss) < popcount(dpb[msk].ff)) {
						dpb[msk].ff = dpb[prev].ff;
					}
					if (popcount(dpb[prev].ss) < popcount(dpb[msk].ss)) {
						dpb[msk].ss = dpb[prev].ss;
					}
				}
			}
			if (popcount(dpb[msk].ss) < popcount(dpb[msk].ff)) {
				dpb[msk].ff = dpb[msk].ss;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		int ans = 0;
		int tar = 0;
		for (int j = 0; j < m; j++) {
			int cnt = freq[j] - bool(a[i] & (1 << j));
			if (cnt > (n / 2)) ans++;
			else if (cnt == (n / 2)) tar |= (1 << j);
		}
		tar ^= ((1 << m) - 1);
		// tar[j] = 1: have or not have doesn't matter; else matters
		// cerr << tar << ' ' << dpb[tar].ff << ' ' << dpb[tar].ss << endl;
		int add = 0;
		if (dpb[tar].ff != -1 && dpf[dpb[tar].ff] != i) {
			add = max(add, m - popcount(dpb[tar].ff));
		}
		if (dpb[tar].ss != -1) {
			add = max(add, m - popcount(dpb[tar].ss));
		}
		ans += add;
		cout << ans << endl;
	}
}
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init(); solve();
}

• 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