oj.uz

답안 #907618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907618 2024-01-16T00:21:37 Z vjudge1 Council (JOI23_council) C++17
0 / 100
 83 ms 31452 KB 
#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=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

# 결과 실행 시간 메모리 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 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 1 ms 348 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 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 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 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 1 ms 348 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 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 75 ms 31336 KB Output is correct
3 Correct 77 ms 31316 KB Output is correct
4 Correct 56 ms 30804 KB Output is correct
5 Correct 83 ms 31452 KB Output is correct
6 Incorrect 60 ms 30800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 75 ms 31336 KB Output is correct
3 Correct 77 ms 31316 KB Output is correct
4 Correct 56 ms 30804 KB Output is correct
5 Correct 83 ms 31452 KB Output is correct
6 Incorrect 60 ms 30800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 75 ms 31336 KB Output is correct
3 Correct 77 ms 31316 KB Output is correct
4 Correct 56 ms 30804 KB Output is correct
5 Correct 83 ms 31452 KB Output is correct
6 Incorrect 60 ms 30800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 75 ms 31336 KB Output is correct
3 Correct 77 ms 31316 KB Output is correct
4 Correct 56 ms 30804 KB Output is correct
5 Correct 83 ms 31452 KB Output is correct
6 Incorrect 60 ms 30800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 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 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 1 ms 348 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 344 KB Output isn't correct
14 Halted 0 ms 0 KB -