Submission #932696

#	Time	Username	Problem	Language	Result	Execution time	Memory
932696		WongChun1234	Genetics (BOI18_genetics)	C++14	27 / 100	2021 ms	5816 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
const int N=4150;
int n,m,k,curr,test,cnt,perm[N],seed[N];
string ipt,a[N];
set<pair<int,int>> ppl,all;
mt19937 rng(1234);
int random(int l,int r){
	return uniform_int_distribution<int>(l,r)(rng);
}
int choose(set<pair<int,int>> &s){
	auto it=s.upper_bound({random(1,1e9),0});
	if (it==s.end()) it=s.begin();
	return (*it).second;
}
int main(){
	cin>>n>>m>>k;
	iota(perm,perm+m,0);
	shuffle(perm,perm+m,rng);
	for (int i=1;i<=n;i++){
		cin>>ipt;
		a[i]=ipt;
		for (int j=0;j<m;j++) a[i][j]=ipt[perm[j]];
		seed[i]=random(1,1e9);
		ppl.insert({seed[i],i});
		all.insert({random(1,1e9),i});
	}
	while (ppl.size()>1){
		curr=choose(ppl);
		do{
			test=choose(all);
		} while (test==curr);
		cnt=0;
		for (int i=0;i<m;i++){
			cnt+=(a[curr][i]!=a[test][i]);
			if (cnt>k||cnt+(m-i-1)<k) break;
		}
		if (cnt!=k) ppl.erase({seed[curr],curr});
	}
	cout<<choose(ppl)<<"\n";
}

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