Submission #1206798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206798		salmon	Council (JOI23_council)	C++20	62 / 100	283 ms	16712 KiB

council

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

int N;
int M;
int lst[300100];
int h;
int vot[22];
pair<int,int> hav[(1<<21) + 5];
pair<pair<int,int>,pair<int,int>> memo[300100];

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 0; i < N; i++){
		int num = 0;
		
		for(int j = 0; j < M; j++){
			scanf(" %d",&h);
		
			num += (h<<j);
	
			vot[j] += h;
		}
		
		lst[i] = num;
	}
	
	int zero = 0;
	int one = 0;
	int def = 0;
	
	for(int i = 0; i < M; i++){
		if(vot[i] - (N)/2 == 0){
			zero += (1<<i);
		}
		else if(vot[i] - N/2 == 1){
			one += (1<<i);
		}
		else if(vot[i] - N/2 > 1)def++;
	}
	
	for(int i = 0; i < (1<<M); i++){
		hav[i] = {-1,-1};
	}
	
	for(int i = 0; i < N; i++){
		if(hav[(~lst[i])&((1<<M) - 1)].first == -1) hav[(~lst[i])&((1<<M) - 1)].first = i;
		else hav[(~lst[i])&((1<<M) - 1)].second = i;
	}
	
	for(int k = 0; k < M; k++){
		for(int i = 0; i < (1<<M); i++){
			if( ((1<<k)&i) > 0){
				if(hav[i^(1<<k)].first == -1) hav[i^(1<<k)] = hav[i];
				else if(hav[i^(1<<k)].second == -1) hav[i^(1<<k)].second = hav[i].first;
			}
		}
	}
	
	for(int i = 0; i < (1<<M); i++){
		if(hav[i].first == -1) memo[i] = {{0,-1},{0,-1}};
		else if(hav[i].second == -1) memo[i] = {{__builtin_popcount(i),hav[i].first },{0 , -1}};
		else memo[i] = {{__builtin_popcount(i),hav[i].first}, {__builtin_popcount(i), hav[i].second} };
	}
	
	for(int k = 0; k < M; k++){
		for(int i = 0; i < (1<<M); i++){
			if( ((1<<k)&i) > 0){
				if(memo[i].first.first < memo[i^(1<<k)].first.first ){
					if(memo[i].first.second == memo[i^(1<<k)].first.second){
						if(memo[i].second.first < memo[i^(1<<k)].second.first){
							memo[i] = memo[i^(1<<k)];
						}
						else{
							memo[i] = {memo[i^(1<<k)].first, memo[i].second};
						}
					}
					else{
						if(memo[i].first.first < memo[i^(1<<k)].second.first){
							memo[i] = memo[i^(1<<k)];
						}
						else{
							memo[i] = {memo[i^(1<<k)].first, memo[i].first};
						}
					}
				}
				else if(memo[i].second.first < memo[i^(1<<k)].first.first ){
					if(memo[i].first.second == memo[i^(1<<k)].first.second ) memo[i].second = max(memo[i^(1<<k)].second, memo[i].second);
					else memo[i].second = memo[i^(1<<k)].first;
				}
			}
		}
	}
	
	/*for(int i = 0; i < (1<<M); i++){
		printf("%b %b %b\n",i,memo[i].first.first,memo[i].second.first);
	}*/
	
	//printf("%12b\n%12b\n",zero,one);
	//for(int i = 0; i  < M; i++) printf("%d\n",vot[i]);
	
	for(int i = 0; i < N; i++){
		int fin = (zero & (~lst[i])) | (one & lst[i]);
		int ans = def + __builtin_popcount((one & (~lst[i])));
		
		//printf("%b %b\n",fin,(one&(~lst[i])));
		//printf("%d\n",memo[fin].second.second);
		
		
		if( i == memo[fin].first.second ) printf("%d\n",memo[fin].second.first + ans);
		else printf("%d\n",memo[fin].first.first + ans);
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
council.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
council.cpp:21:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 0 / 22