Submission #240563

#	Time	Username	Problem	Language	Result	Execution time	Memory
240563		dsjong	Genetics (BOI18_genetics)	C++14	0 / 100	65 ms	16504 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int diff[5000][5000], cnt[5000];
char a[5000][5000];
bool check(int x){
	bool b=true;
	for(int i=1;i<=n;i++){
		if(i==x) continue;
		int cnt=0;
		for(int j=1;j<=m;j++){
			if(a[x][j]!=a[i][j]) cnt++;
		}
		diff[x][i]=diff[i][x]=cnt;
		if(cnt!=k) b=false;
	}
	return b;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	if(n<=1){
		for(int i=1;i<=n;i++){
			if(check(i)){
				cout<<i;
				return 0;
			}
		}
	}
	if(check(1)){
		cout<<1;
		return 0;
	}
	int x;
	for(int i=2;i<=n;i++){
		//cout<<diff[i][1]<<" "<<diff[1][i]<<endl;
		if(diff[1][i]==k){
			if(check(i)){
				cout<<i;
				return 0;
			}
			else{
				x=i;
				break;
			}
		}
	}
	for(int j=1;j<=m;j++){
		if(a[1][j]=='A') cnt[j]++;
		if(a[x][j]=='A') cnt[j]++;
	}
	vector<int>v;
	v.push_back(1);
	v.push_back(x);
	for(int i=1;i<=n;i++){
		if(i==1 || i==x) continue;
		if(diff[i][1]==k && diff[i][x]==k){
			v.push_back(i);
			for(int j=1;j<=m;j++){
				if(a[i][j]=='A') cnt[j]++;
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(cnt[i]==1){
			for(int j:v){
				if(a[j][i]=='A'){
					cout<<j;
					return 0;
				}
			}
		}
		else if(cnt[i]==(int)v.size()-1){
			for(int j:v){
				if(a[j][i]=='C'){
					cout<<j;
					return 0;
				}
			}
		}
	}
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26