Submission #566292

#	Time	Username	Problem	Language	Result	Execution time	Memory
566292		hohohaha	Genetics (BOI18_genetics)	C++17	27 / 100	2052 ms	4544 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); 

const int maxn = 4105; 
int n, m, k; 
string s[maxn]; 
bool ok[maxn]; 

int comp(string &s, string &t) {  
	int cnt = 0; fori(i, 0, m - 1) cnt += s[i] != t[i]; 
	return cnt; 
}

signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cin >> n >> m >> k; 
	fori(i, 1, n) cin >> s[i]; 
	vector<int> ord(n, 0); 
	iota(begin(ord), end(ord), 1); 
	shuffle(begin(ord), end(ord), rng); 
	
	fori(idx, 0, min(n - 1, 5) ) {
		int i = rng() % n + 1; 
		fori(j, 1, n) { 
			if(comp(s[i], s[j]) != k) ok[j] = 0; 
		}
	}
	
	fill(ok, ok + n + 1, 1); 
	 for(int i: ord) { 
	 	for(int j: ord) {
		 	if(!ok[i]) break;  
	 		if(i == j) continue; 
	 	 	if(comp(s[i], s[j]) != k) { 
	 	 		ok[i] = ok[j] = 0; 
	 	 	}
	 	 }
	 	if(ok[i]) { 
	 		cout << i; 
	 		return 0; 
	 	}
	 }
}

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