Submission #1213243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213243		KK_1729	Council (JOI23_council)	C++20	6 / 100	350 ms	88468 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;
}

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;
			}
		}
	}


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

			vector<int> candid = {-1, -1};

			if (f[i].size() > 0 && __builtin_popcount(i) == k){
				auto it = f[i].begin();
				candid.pb(*it);
				if (f[i].size() > 1 && __builtin_popcount(i) == k){
					it++;
					candid.pb(*it);
				}
			}
			for (int j = 0; j < m; j++){
				if (i & (1 << j)){
					candid.pb(dp[k][i^(1 << j)].first);
					candid.pb(dp[k][i^(1 << j)].second);
				}
			}
			sort(all(candid));
			reverse(all(candid));
			dp[k][i] = make_pair(candid[0], candid[1]);
		}
	}
	// 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: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22