Submission #874638

#	Time	Username	Problem	Language	Result	Execution time	Memory
874638		NK_	Council (JOI23_council)	C++17	100 / 100	1182 ms	31928 KiB

council

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

#define f first
#define s second
#define mp make_pair

#define sz(x) int(x.size())

using pi = pair<int, int>;
using ll = long long;

template<class T> using V = vector<T>;

using vi = V<int>;
using vpi = V<pi>;

const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M; cin >> N >> M;

	vi A(N); for(auto& x : A) {
		for(int i = 0; i < M; i++) {
			int v; cin >> v;
			x ^= v << i;
		}
	}

	int MX = (1 << M), MSK = MX - 1;
	vi B = A; for(auto& x : B) x ^= MSK;

	vi C(M, -(N / 2));
	for(int i = 0; i < M; i++) for(int x = 0; x < N; x++) C[i] += (A[x] >> i) & 1;

	vpi X(MX, mp(0, -2)), X2(MX, mp(0, -2)); // update to store two largest PCTs and where its from????

	for(int c = 0; c < N; c++) {
		int x = B[c];
		// for(int i = 0; i < M; i++) {
		// 	cout << ((x >> i) & 1) << " ";
		// }	
		// cout << endl;


		if (X[x].s == -2) X[x] = mp(__builtin_popcount(x), c);
		else X[x] = mp(__builtin_popcount(x), -1);
	}



	for(int i = 0; i < M; i++) for(int s = MX - 1; s >= 0; s--) {
		if ((s >> i) & 1) {
			int ns = s ^ (1 << i); // ns <= s
			vpi S = vpi{mp(X[s].f - 1, X[s].s), mp(X2[s].f - 1, X2[s].s), X[ns], X2[ns]}; 
			sort(rbegin(S), rend(S));

			X[ns] = S.front();
			for(int x = 0; x < 4; x++) if (S[x].s != X[ns].s) { X2[ns] = S[x]; break; }
		}
	}

	// for(int x = 0; x < MX; x++) cout << x << " => " << X[x] << endl;

	for(int i = 0; i < M; i++) for(int s = 0; s < MX; s++) {
		if ((s >> i) & 1) {
			int ns = s ^ (1 << i); // ns => s
			vpi S = vpi{X[s], X2[s], X[ns], X2[ns]}; 
			sort(rbegin(S), rend(S));

			X[s] = S.front();
			for(int x = 0; x < 4; x++) if (S[x].s != X[s].s) { X2[s] = S[x]; break; }
		}
	}

	// for(int x = 0; x < MX; x++) cout << x << " => " << X[x] << endl;

	for(int i = 0; i < N; i++) {
		for(int x = 0; x < M; x++) C[x] -= (A[i] >> x) & 1;
		// for(auto& x : C) cout << x << " ";
		// cout << nl;

		int c = 0, yes = 0;
		for(int x = 0; x < M; x++) {
			if (C[x] >= 1) yes++;
			else if (C[x] == 0) c ^= (1 << x);
			// cout << ((c >> x) & 1) << " ";
		}
		// cout << nl;

		// cout << X[c].f << " " << X[c].s << nl;
		cout << yes + (X[c].s == i ? X2[c].f : X[c].f) << nl;
		for(int x = 0; x < M; x++) C[x] += (A[i] >> x) & 1;
	}



	exit(0-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