Submission #1213256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213256		KK_1729	Council (JOI23_council)	C++17	100 / 100	2025 ms	612700 KiB

council

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
// chmax(pair<int, int> x, pair<int, int> y){
// 	if ()
// }
void solve(){

	int n, m; cin >> n >> m;
	vector<vector<int>> o(n);

	vector<int> a(n);
	vector<int> count(m);
	vector<set<int>> f(1 << m);
	FOR(i,0,n){
		FOR(j,0,m){
			int x; cin >> x;
			o[i].pb(x);
			a[i] += ((1-x) << j);
			if (x) count[j]++;
		}
		f[a[i]].insert(i);
	}

	
	for (int i = (1ll << m) - 1; i >= 0; i--){
		if (f[i].size() >= 2) continue;
		for (int j = 0; j < m; j++){
			if ((i & (1 << j)) == 0){
				for (auto x: f[i|(1 << j)]){
					f[i].insert(x);
					if (f[i].size() >= 2) break;
				}
				
				if (f[i].size() >= 2) break;
			}
		}
	}


	vector<vector<pair<int, int>>> dp(m+1, vector<pair<int, int>>(1 << m));
	for (int i = 0; i < (1ll << m); i++){
		for (int k = 0; k <= m; k++){

			set<int, greater<int>> candid;
			// candid.insert(-1);

			if (f[i].size() > 0 && __builtin_popcount(i) == k){
				auto it = f[i].begin();
				candid.insert(*it);
				if (f[i].size() > 1 && __builtin_popcount(i) == k){
					it++;
					candid.insert(*it);
				}
			}
			for (int j = 0; j < m; j++){
				if (i & (1ll << j)){
					if (dp[k][i^(1 << j)].first != -1) candid.insert(dp[k][i^(1 << j)].first);
					if (dp[k][i^(1 << j)].second != -1) candid.insert(dp[k][i^(1 << j)].second);
					if (candid.size() >= 2) break;
				}
			}

			if (candid.size() == 0){
				dp[k][i] = make_pair(-1, -1);
			}
			if (candid.size() == 1){
				dp[k][i] = make_pair(*candid.begin(), -1);
			}
			if (candid.size() >= 2){
				int first = *candid.begin();
				candid.erase(candid.begin());
				int sec = *candid.begin();
				dp[k][i] = make_pair(first, sec);
			}
		}
	}
	// printVector(count);
	FOR(i,0,n){
		vector<int> c(m);
		FOR(j,0,m) c[j] = count[j];
		FOR(j,0,m){
			if (o[i][j] == 1) c[j]--;
		}
		int e = 0;
		int p = 0;
		FOR(j,0,m){
			if (c[j] == n/2) e |= (1 << j);
			if (c[j] > n/2) p++;
		}
		// cout << e << endl;
		int ans = 0;
		int v = 0;
		FOR(j,1,m+1){
			if ((dp[j][e].first != -1 && dp[j][e].first != i) || (dp[j][e].second != -1 && dp[j][e].second != i)) v = j;
		}


		// cout << e << endl;
		cout << p+v << endl;
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) 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