Submission #532688

#	Time	Username	Problem	Language	Result	Execution time	Memory
532688		fatemetmhr	Genetics (BOI18_genetics)	C++17	0 / 100	235 ms	15020 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back

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


const int maxn5 = 3e5 + 10;


string s[maxn5];
int av[maxn5], per[maxn5];
int n, m, k;

inline bool ok(int i, int j){
	int cnt = 0;
	for(int z = 0; z < m && cnt <= k; z++)
		cnt += (s[i][z] != s[j][z]);
	return cnt == k;
}

inline void check(int v){
	for(int i = 0; i < n; i++)
		av[i] = i;
	shuffle(av, av + n, rng);
	for(int i = 0; i < n; i++) 
		if(v != per[i] && !ok(v, per[i]))
			return;
	cout << v + 1 << endl;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		cin >> s[i];
		per[i] = i;
	}

	int sz = n;
	while(true){
		int id = rng() % sz;
		check(per[id]);
		for(int i = id + 1; i < n; i++)
			per[i - 1] = per[i];
		sz--;
	}

}

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