Submission #1027783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027783		Unforgettablepl	Council (JOI23_council)	C++17	100 / 100	841 ms	207956 KiB

council

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin >> n >> m;
	vector<vector<int>> a(n+1,vector<int>(m+1));
	vector<int> votes(m+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j])votes[j]++;
		}
	}
	int majority = n/2;
	vector<vector<int>> arr(n+1); // this is processed
	int offset = 0;
	vector<int> voters;
	for(int i=1;i<=m;i++){
		if(majority+1<votes[i])offset++;
		if(votes[i]<majority or majority+1<votes[i])continue;
		voters.emplace_back(votes[i]);
	}
	auto combine = [&](pair<int,int> &a,pair<int,int> b){
		pair<int,int> ans = {-1,-1};
		if(a.first<b.first){
			ans.first = b.first;
			swap(b.first,b.second);
		} else {
			ans.first = a.first;
			swap(a.first,a.second);
		}
		if(a.first<b.first){
			ans.second = b.first;
			swap(b.first,b.second);
		} else {
			ans.second = a.first;
			swap(a.first,a.second);
		}
		return ans;
	};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(votes[j]<majority or majority+1<votes[j])continue;
			arr[i].emplace_back(a[i][j]);
		}
	}
	m = arr[1].size(); // this is processed
	vector<pair<int,int>> DPfront(1<<m,{-1,-1});
	for(int i=1;i<=n;i++){
		int curr = 0;
		for(int j=0;j<m;j++)if(arr[i][j]==0)curr|=(1<<j);
		DPfront[curr] = combine(DPfront[curr],{i,-1});
	}
	for(int bit=0;bit<m;bit++)for(int i=(1<<m)-1;i>=0;i--)if((i&(1<<bit))==0){
		DPfront[i]=combine(DPfront[i],DPfront[i|(1<<bit)]);
	}
	vector<pair<pair<int,int>,pair<int,int>>> DPback(1<<m,{{0,-1},{0,-1}});
	auto combine_good = [&](pair<pair<int,int>,pair<int,int>> &a,pair<pair<int,int>,pair<int,int>> &b){
		pair<pair<int,int>,pair<int,int>> ans = {{0,-1},{0,-1}};
		vector<pair<int,int>> things = {a.first,a.second,b.first,b.second};
		sort(things.rbegin(),things.rend());
		ans.first = things[0];
		for(int i=1;i<4;i++){
			if(things[i].second!=ans.first.second){ans.second=things[i];break;}
		}
		return ans;
	};
	for(int i=0;i<(1<<m);i++){
		if(DPfront[i].first!=-1){
			DPback[i].first={__builtin_popcount(i),DPfront[i].first};
			if(DPfront[i].second!=-1){
				DPback[i].second={__builtin_popcount(i),DPfront[i].second};
			}
		}
	}
	for(int bit=0;bit<m;bit++)for(int i=0;i<(1<<m);i++)if(i&(1<<bit)){
		DPback[i] = combine_good(DPback[i],DPback[i^(1<<bit)]);
	}
	for(int i=1;i<=n;i++){
		int curr = 0;
		int my = 0;
		for(int j=0;j<m;j++){
			if(voters[j]==majority){
				if(arr[i][j]==0)curr|=(1<<j);
			} else if (voters[j]==majority+1){
				if(arr[i][j]==1)curr|=(1<<j);
				else my++;
			}
		}
		int ans;
		if(DPback[curr].first.second!=i)ans=DPback[curr].first.first;
		else ans=DPback[curr].second.first;
		cout << offset+ans+my << '\n';
	}
}

• 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