Submission #728890

#	Time	Username	Problem	Language	Result	Execution time	Memory
728890		WonderfulWhale	Genetics (BOI18_genetics)	C++17	0 / 100	2074 ms	5708 KiB

genetics

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

#define int int64_t
#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];

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

	srand(2137);

	int n, m, K;
	cin >> n >> m >> K;
	for(int i=1;i<=n;i++) cin >> tab[i];
	vector<int> v1;
	vector<int> v2;
	for(int i=1;i<=n;i++) v1.pb(i), v2.pb(i);
	random_shuffle(all(v1));
	random_shuffle(all(v2));
	while(true) {
		vector<int> nv;
		bool ans = true;
		for(int i=0;i<n;i++) {
			if(v1.back()==v2[i]) continue;
			int cnt = 0;
			for(int j=0;j<m;j++) {
				if(tab[v1.back()][j]!=tab[v2[i]][j]) cnt++;
			}
			if(cnt!=K) {
				v2[i] = false;
				ans = false;
				break;
			} else if(!vis[v2[i]]) {
				nv.pb(v2[i]);
			}
		}
		if(ans) {
			cout << v1.back() << "\n";
			return 0;
		} else {
			vis[v1.back()] = false;
		}
		v1 = nv;
	}
}

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