Submission #728944

#	Time	Username	Problem	Language	Result	Execution time	Memory
728944		WonderfulWhale	Genetics (BOI18_genetics)	C++17	19 / 100	2070 ms	134688 KiB

genetics

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

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

string tab[4109];
bool vis[4109];

queue<int> Q;
int dp[4109][4109];

int ile[4109][26];
int sum[4109];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	memset(dp, -1, sizeof(dp));

	int n, m, K;
	cin >> n >> m >> K;
	for(int i=1;i<=n;i++) cin >> tab[i];
	for(int i=1;i<=n;i++) {
		for(int j=0;j<m;j++) {
			ile[j][tab[i][j]-'A']++;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<m;j++) {
			for(int k=0;k<4;k++) {
				if(tab[i][j]!='A'+k) {
					sum[i]+=ile[j][k];
				}
			}
		}
	}
	for(int i=1;i<=n;i++) {
		if(sum[i]!=K*(n-1)) vis[i] = true;
	}
	vector<int> v;
	for(int i=1;i<=n;i++) v.pb(i);
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			Q.push(i);
			vis[i] = true;
			break;
		}
	}
	while(true) {
		int x = Q.front();
		Q.pop();
		bool ans = true;
		random_shuffle(all(v));
		for(int i=0;i<n;i++) {
			if(v[i]==x) continue;
			int cnt = dp[v[i]][x];
			if(cnt==-1) {
				cnt = 0;
				for(int j=0;j<m;j++) {
					if(tab[x][j]!=tab[v[i]][j]) cnt++;
				}
			}
			dp[v[i]][x] = dp[x][v[i]] = cnt;
			if(cnt==K) {
				if(!vis[v[i]]) {
					vis[v[i]] = true;
					Q.push(v[i]);
				}
			} else {
				vis[v[i]] = true;
				ans = false;
			}
		}
		if(ans) {
			cout << x << "\n";
			return 0;
		}
	}
}

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