Submission #776255

#	Time	Username	Problem	Language	Result	Execution time	Memory
776255		Arturgo	Council (JOI23_council)	C++14	100 / 100	2288 ms	186324 KiB

council

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

const int MAX_M = 20;
using bits = bitset<MAX_M>;

vector<bits> votes;

list<int> submasks[(1 << MAX_M)];
vector<pair<int, int>> surmasks[(1 << MAX_M)];

void add(list<int> l[], bits mask, int sl) {
	list<int>& lst = l[mask.to_ulong()];
	
	if(lst.size() >= 2) return;
	
	if(lst.empty()) {
		lst.push_back(sl);
		return;
	}
	
	if(lst.back() != sl) {
		lst.push_back(sl);
		return;
	}
}

void add(vector<pair<int, int>> l[], bits mask, pair<int, int> sl) {
	vector<pair<int, int>>& lst = l[mask.to_ulong()];
	
	for(int i = 0;i < (int)lst.size();i++) {
		if(lst[i].second == sl.second) {
			lst[i].first = max(sl.first, lst[i].first);
			return;
		}
		
		if(lst[i].first < sl.first) {
			swap(lst[i], sl);
		}
	}
	
	lst.push_back(sl);
	if(lst.size() > 2) lst.pop_back();
}

int main() {
	int N, M;
	cin >> N >> M;
	
	vector<int> nbVotes(MAX_M, 0);
	
	for(int i = 0;i < N;i++) {
		bits v;
		for(int j = 0;j < M;j++) {
			int ok;
			cin >> ok;
			v[j] = ok;
			nbVotes[j] += ok;
		}
		votes.push_back(v);
		
		add(submasks, bits((1 << M) - 1) ^ v, i);
	}
	
	for(int j = 0;j < M;j++) {
		for(int m = 0;m < (1 << MAX_M);m++) {
			bits mask_false = m;
			if(mask_false[j]) continue;
			
			bits mask_true = m;
			mask_true[j] = true;
			
			for(int sol : submasks[mask_true.to_ulong()])
				add(submasks, mask_false, sol);
		}
	}
	
	/*for(int m = 0;m < (1 << MAX_M);m++) {
		if(!submasks[m].empty()) {
			cout << bits(m) << " ";
			
			for(int sl : submasks[m]) {
				cout << sl << " ";
			}
			cout << endl;
		}
	}*/
	
	for(int m = 0;m < (1 << MAX_M);m++) {
		if(!submasks[m].empty()) {
			for(int sl : submasks[m]) {
				surmasks[m].push_back({bits(m).count(), sl});
			}
		}
	}
	
	for(int j = 0;j < M;j++) {
		for(int m = 0;m < (1 << MAX_M);m++) {
			bits mask_false = m;
			if(mask_false[j]) continue;
			
			bits mask_true = m;
			mask_true[j] = true;
			
			for(pair<int, int> sol : surmasks[mask_false.to_ulong()])
				add(surmasks, mask_true, sol);
		}
	}
	
	/*for(int m = 0;m < (1 << 3);m++) {
		if(!surmasks[m].empty()) {
			cout << bits(m) << " ";
			
			for(pair<int, int> sl : surmasks[m]) {
				cout << "{" << sl.first << "," << sl.second << "}" << " ";
			}
			cout << endl;
		}
	}*/
	
	for(int i = 0;i < N;i++) {
		bits imps;
		int nbOks = 0;
		
		for(int j = 0;j < M;j++) {
			if(nbVotes[j] - (int)votes[i][j] < N / 2) {
				
			}
			else if(nbVotes[j] - (int)votes[i][j] > N / 2) {
				nbOks++;
			}
			else {
				imps[j] = true;
			}
		}
		
		for(pair<int, int> m : surmasks[imps.to_ulong()]) {
			if(m.second != i) {
				cout << nbOks + m.first << endl;
				break;
			}
		}
	}
	
	return 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