Submission #907631

#	Time	Username	Problem	Language	Result	Execution time	Memory
907631		vjudge1	Council (JOI23_council)	C++17	22 / 100	4035 ms	71764 KiB

council

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

struct trie{
	int s[2];
	int numb=0;
}tre[300000*10];

int b[300100][25],msum[25];
int cnt=0;
int n,m;
int nw[25];

void insert(int which){
	int nw=0;
	for (int i=1;i<=m;i++){
		int tp=b[which][i];
		if (!tre[nw].s[tp]){
			tre[nw].s[tp]=++cnt;
		}
		//printf("%d %d\n",tp,tre[nw].s[tp]);
		nw=tre[nw].s[tp];
	}
	tre[nw].numb++;
}

int fd(int level,int tnum,int l,int cur,int ult[]){
	if (l<0){
		return -99999;
	}
	if (level>m){
		bool same=true;
		for (int i=1;i<=m;i++){
			if (ult[i]!=b[cur][i]){
				same=false;
			}
		}
		if (same&&tre[tnum].numb<=1) return -99999;
		int ans=0;
		for (int i=1;i<=m;i++){
			if (ult[i]==0&&nw[i]==1){
				ans++;
			}
		}
		return ans;
	}
	int ans=0;
	if (tre[tnum].s[0]){
		ult[level]=0;
		ans=max(ans,fd(level+1,tre[tnum].s[0],l,cur,ult));
	}
	int emmmm=0;
	if (tre[tnum].s[1]){
		ult[level]=1;
		int tp=0;
		if (nw[level]==1){
			emmmm=1;
		}
		tp=fd(level+1,tre[tnum].s[1],l-emmmm,cur,ult);
		ans=max(tp,ans);
	}
	//printf("%d %d %d\n",level,l,ans);
	return ans;
}

int main(){
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++){
		for (int p=1;p<=m;p++){
			scanf("%d",&b[i][p]);
			msum[p]+=b[i][p];
		}
		insert(i);
	}
	for (int i=1;i<=n;i++){
		int ans=0,ct=0;
		memset(nw,0,sizeof nw);
		for (int p=1;p<=m;p++){
			msum[p]-=b[i][p];
			if (msum[p]==n/2){
				nw[p]=1;
				ct++;
			}
			else if (msum[p]>n/2){
				ans++;
			}
		}
		int tpans=0;
		for (int p=0;p<=ct;p++){
			int emtary[30];
			memset(emtary,0,sizeof emtary);
			int tps=fd(1,0,p,i,emtary);
			if (tps>0){
				tpans=tps;
				break;
			}
		}
		for (int p=1;p<=m;p++){
			msum[p]+=b[i][p];
		}
		printf("%d\n",ans+tpans);
	}
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
council.cpp:70:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |    scanf("%d",&b[i][p]);
      |    ~~~~~^~~~~~~~~~~~~~~

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