Submission #920260

#	Time	Username	Problem	Language	Result	Execution time	Memory
920260		vjudge1	Council (JOI23_council)	C++17	100 / 100	1012 ms	61020 KiB

council

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

typedef unsigned long long ll;
#define MAXN (int)pow(2,21)+10

int pc(ll x){
	int now=0;
	while(x){
		now++;
		x^=(x&(-x));
	}
	return now;
}

ll sm[25];
ll num[300010],pnums[300010],pans[300010];
int gs[MAXN];
ll omx[MAXN],osmx[MAXN];
//ll umx[MAXN],usmx[MAXN];

int main(){
	//freopen("try.in","r",stdin);
	//freopen("try2.out","w",stdout);
	memset(gs,0,sizeof gs);
	memset(omx,0,sizeof omx);
	memset(osmx,0,sizeof osmx);
	//memset(umx,0,sizeof umx);
	//memset(usmx,0,sizeof usmx);
	memset(num,0,sizeof num);
	//printf("%d %d %d",((int)pow(2,21)-1)-3,6^((int)pow(2,21)-1),1023^((int)pow(2,21)-1));
	int n,m; scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++){
		for (int p=1;p<=m;p++){
			int tp; scanf("%d",&tp);
			sm[p]+=tp;
			num[i]+=(tp<<(p-1));
		}
		ll tp=(1<<m)-num[i]-1;
		omx[tp]=tp;
		gs[tp]++;
		//printf("%d %lld\n",i,tp);
		//umx[num[i]]=tp;
	}
	for (int i=1;i<=n;i++){
		ll wfj=0;
		ll tp;
		for (int p=1;p<=m;p++){
			tp=sm[p];
			tp-=(num[i]>>(p-1))&1;
			if (tp==(n/2)){
				wfj+=(1<<(p-1));
			}else if (tp>(n/2)){
				pans[i]++;
			}
		}
		pnums[i]=wfj;
	}
	/*
	for (int i=1;i<=n;i++){
		printf("%lld %lld %d\n",pans[i],pnums[i],n/2);
	}*/
	for (int i=0;i<m;i++){
		for (int p=(1<<m)-1;p>=0;p--){
			if (((p>>i)&1)==1){
				int tp=p-(1<<i);
				//printf("%d %d\n",p,tp);
				if (pc(omx[p]&tp)>pc(osmx[tp]&tp)&&(omx[p]!=omx[tp])){
					osmx[tp]=omx[p];
					if (pc(osmx[tp]&tp)>pc(omx[tp]&tp)) swap(omx[tp],osmx[tp]);
					//printf("%d %d %d %d %d\n",omx[p],tp,osmx[tp],omx[tp],osmx[tp]);	
				}
				if (pc(osmx[p]&tp)>pc(osmx[tp]&tp)&&(osmx[p]!=omx[tp])){
					osmx[tp]=osmx[p];
					if (pc(osmx[tp]&tp)>pc(omx[tp]&tp)) swap(omx[tp],osmx[tp]);
					//printf("%d %d %d %d %d\n",omx[p],tp,osmx[tp],omx[tp],osmx[tp]);
				}
			}
		}
	}
	for (int i=0;i<m;i++){
		for (int p=0;p<(1<<m);p++){
			if (((p>>i)&1)==0){
				int tp=p+(1<<i);
				//printf("%d %d\n",p,tp); 
				if (pc(omx[p]&tp)>pc(osmx[tp]&tp)&&(omx[p]!=omx[tp])){
					osmx[tp]=omx[p];
					if (pc(osmx[tp]&tp)>pc(omx[tp]&tp)) swap(omx[tp],osmx[tp]);
					//printf("%d %d %d %d %d\n",omx[p],tp,osmx[tp],omx[tp],osmx[tp]);	
				}
				if (pc(osmx[p]&tp)>pc(osmx[tp]&tp)&&(osmx[p]!=omx[tp])){
					osmx[tp]=osmx[p];
					if (pc(osmx[tp]&tp)>pc(omx[tp]&tp)) swap(omx[tp],osmx[tp]);
					//printf("%d %d %d %d %d\n",omx[p],tp,osmx[tp],omx[tp],osmx[tp]);
				}
			}
		}
	}
	
	for (int i=1;i<=n;i++){
		int itp=pnums[i];
		int tp1=omx[itp];
		//int tp2=umx[itp];
		/*
		if (((1<<m)-1-tp1)==num[i]){
			//printf("%d %d\n",tp1,num[i]);
			tp1=osmx[itp];
		}*/
		if ((((1<<m)-1-tp1)==num[i])&&(gs[tp1]==1)){
			//printf("tl");
			tp1=osmx[itp];
		}
		/*
		if (tp2==num[i]){
			tp2=usmx[itp];
		}*/
		//printf("%d %d %d %d %lld %lld %lld %lld\n",i,gs[tp1],pc(tp1&itp),pans[i],tp1,itp,num[i],(1<<m)-1-tp1);
		printf("%d\n",pc(tp1&itp)+pans[i]);
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:51:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   51 |    if (tp==(n/2)){
      |        ~~^~~~~~~
council.cpp:53:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   53 |    }else if (tp>(n/2)){
      |              ~~^~~~~~
council.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
  109 |   if ((((1<<m)-1-tp1)==num[i])&&(gs[tp1]==1)){
      |        ~~~~~~~~~~~~~~^~~~~~~~
council.cpp:118:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long unsigned int'} [-Wformat=]
  118 |   printf("%d\n",pc(tp1&itp)+pans[i]);
      |           ~^    ~~~~~~~~~~~~~~~~~~~
      |            |               |
      |            int             ll {aka long long unsigned int}
      |           %lld
council.cpp:32:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  int n,m; scanf("%d %d",&n,&m);
      |           ~~~~~^~~~~~~~~~~~~~~
council.cpp:35:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |    int tp; scanf("%d",&tp);
      |            ~~~~~^~~~~~~~~~

• 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