Submission #1046555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046555		GusterGoose27	Council (JOI23_council)	C++17	100 / 100	537 ms	30548 KiB

council

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5+5;
const int MAXM = 20;

int votes[MAXN];
int vsum[MAXM];
int n, m;

typedef array<int, 2> ar2;

struct mx_pair {
	ar2 a, b;
	mx_pair() {
		a = b = {0, -1};
	}
	void ins(ar2 oth) {
		if (oth[0] == 0) return;
		if (oth[1] == a[1]) {
			a[0] = max(a[0], oth[0]);
		}
		else if (oth[1] == b[1]) {
			b[0] = max(b[0], oth[0]);
			if (b[0] > a[0]) swap(a, b);
		}
		else if (oth[0] >= a[0]) {
			b = a;
			a = oth;
		}
		else if (oth[0] > b[0]) b = oth;
	}
	void ins(mx_pair oth) {
		ins(oth.a); ins(oth.b);
	}
	mx_pair add(int v) {
		mx_pair cpy;
		cpy.a = a;
		cpy.b = b;
		cpy.a[0] += v;
		cpy.b[0] += v;
		return cpy;
		// a[0] += v;
		// b[0] += v;
	}
};

mx_pair bst[1<<MAXM];

bool get(int i, int j) {
	return (i&(1<<j))>0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			bool b; cin >> b;
			votes[i] += b*(1<<j);
			vsum[j] += b;
		}
		bst[((1<<m)-1)&(~votes[i])].ins({m - __builtin_popcount(votes[i]), i});
	}
	for (int i = (1<<m)-2; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			if (!get(i, j)) bst[i].ins(bst[i+(1<<j)].add(-1));
		}
	}
	for (int i = 1; i < (1<<m); i++) {
		for (int j = 0; j < m; j++) {
			if (get(i, j)) bst[i].ins(bst[i-(1<<j)]);
		}
	}
	for (int i = 0; i < n; i++) {
		int cur_mask = 0;
		int def = 0;
		for (int j = 0; j < m; j++) {
			if (vsum[j]-get(votes[i], j) == n/2) cur_mask += (1<<j);
			else if (vsum[j]-get(votes[i], j) > n/2) def++;
		}
		int cur_val = __builtin_popcount((~votes[i])&cur_mask);
		cout << def + (bst[cur_mask].a[1] == i ? bst[cur_mask].b[0] : bst[cur_mask].a[0]) << '\n';
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:83:7: warning: unused variable 'cur_val' [-Wunused-variable]
   83 |   int cur_val = __builtin_popcount((~votes[i])&cur_mask);
      |       ^~~~~~~

• 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