Submission #907620

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
907620	2024-01-16T00:23:06 Z	vjudge1	Council (JOI23_council)	C++17	0 / 100	81 ms	30336 KB

council

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

struct trie{
	int s[2];
}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];
	}
}

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) 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

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

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	8 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	3 ms	348 KB	Output is correct
13	Incorrect	0 ms	348 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	8 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	3 ms	348 KB	Output is correct
13	Incorrect	0 ms	348 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #3

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	72 ms	30336 KB	Output is correct
3	Correct	70 ms	30332 KB	Output is correct
4	Correct	55 ms	30288 KB	Output is correct
5	Correct	81 ms	30288 KB	Output is correct
6	Incorrect	58 ms	30292 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	72 ms	30336 KB	Output is correct
3	Correct	70 ms	30332 KB	Output is correct
4	Correct	55 ms	30288 KB	Output is correct
5	Correct	81 ms	30288 KB	Output is correct
6	Incorrect	58 ms	30292 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	72 ms	30336 KB	Output is correct
3	Correct	70 ms	30332 KB	Output is correct
4	Correct	55 ms	30288 KB	Output is correct
5	Correct	81 ms	30288 KB	Output is correct
6	Incorrect	58 ms	30292 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	72 ms	30336 KB	Output is correct
3	Correct	70 ms	30332 KB	Output is correct
4	Correct	55 ms	30288 KB	Output is correct
5	Correct	81 ms	30288 KB	Output is correct
6	Incorrect	58 ms	30292 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	8 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	3 ms	348 KB	Output is correct
13	Incorrect	0 ms	348 KB	Output isn't correct
14	Halted	0 ms	0 KB	-