Submission #728962

#	Time	Username	Problem	Language	Result	Execution time	Memory
728962		WonderfulWhale	Genetics (BOI18_genetics)	C++17	74 / 100	2081 ms	103196 KiB

genetics

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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[2][4109][26];
int sum[2][4109];

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

	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[i%2][j][tab[i][j]-'A']++;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<m;j++) {
			for(int k:{0,2,6,19}) {
				if(tab[i][j]!='A'+k) {
					sum[0][i]+=ile[0][j][k];
					sum[1][i]+=ile[1][j][k];
				}
			}
		}
	}
	int M = (n+1)/2;
	for(int i=1;i<=n;i++) {
		if((sum[1][i]!=M*K&&sum[1][i]!=(M-1)*K)||(sum[0][i]!=(n-M)*K&&sum[0][i]!=(n-M-1)*K)) 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: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 0 / 26