Submission #1206755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206755		salmon	Council (JOI23_council)	C++20	0 / 100	44 ms	2120 KiB

council

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

int N;
int M;
int lst[300100];
int h;
int vot[22];
int hav[(1<<20) + 5];
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 def++;
	}
	
	for(int i = 0; i < N; i++){
		hav[(~lst[i])&((1<<M) - 1)]++;
		hav[(~lst[i])&((1<<M) - 1)] = min(hav[(~lst[i])&((1<<M) - 1)],2);
	}
	
	for(int k = 0; k < N; k++){
		for(int i = 0; i < (1<<M); i++){
			if( ((1<<k)&i) > 0){
				hav[i^(1<<k)] += hav[i];
				hav[i^(1<<k)] = min(hav[i^(1<<k)],2);
			}
		}
	}
	
	for(int i = 0; i < (1<<M); i++){
		if(hav[i] == 1) memo[i] = {__builtin_popcount(i),0};
		else if(hav[i] == 2) memo[i] = {__builtin_popcount(i), __builtin_popcount(i)};
		else memo[i] = {0,0};
	}
	
	for(int k = 0; k < N; k++){
		for(int i = 0; i < (1<<M); i++){
			if( ((1<<k)&i) > 0){
				if(memo[i].first < memo[i^(1<<k)].first ){
					if(memo[i].first < memo[i^(1<<k)].second){
						memo[i] = memo[i^(1<<k)];
					}
					else{
						memo[i] = {memo[i^(1<<k)].first, memo[i].first};
					}
				}
				else if(memo[i].second < memo[i^(1<<k)].first ) memo[i].second = memo[i^(1<<k)].first;
			}
		}
	}
	
	for(int i = 0; i < N; i++){
		int fin = (zero & (~lst[i])) | (one & lst[i]);
		int ans = def + __builtin_popcount((one & (~lst[i])));
		
		//printf("%d %d\n",fin,ans);
		
		if( __builtin_popcount( ((~lst[i])&((1<<M) - 1)) & fin) == memo[fin].first ) printf("%d\n",memo[fin].second + ans);
		else printf("%d\n",memo[fin].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: 0 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22