Submission #810764

#	Time	Username	Problem	Language	Result	Execution time	Memory
810764		vjudge1	Genetics (BOI18_genetics)	C++17	0 / 100	2070 ms	5168 KiB

genetics

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ordered_set st;
ll N,M,K;
string s[5005];
bool b[5005];
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main(){
	cin>>N>>M>>K;
	for(int i=0;i<N;i++){
		cin>>s[i];
		st.insert(i);
	}
	while(st.size()>2){
		ll x=rng()%st.size();
		ll y=rng()%st.size();
		if(x==y){
			continue;
		}
		ll cnt=0;
		for(int j=0;j<M;j++){
			if(s[x][j]!=s[y][j]){
				cnt++;
			}
		}
		if(cnt!=K){
			st.erase(x);
			st.erase(y);
		}
	}
	if(st.size()==1){
		cout<<*st.find_by_order(0)+1<<endl;
	}
	else{
		ll x=*st.find_by_order(0);
		bool ok=true;
		for(int i=0;i<N;i++){
			if(i==x){
				continue;
			}
			ll cnt=0;
			for(int j=0;j<M;j++){
				if(s[i][j]!=s[x][j]){
					cnt++;
				}
			}
			if(cnt!=K){
				ok=false;
				break;
			}
		}
		if(ok){
			cout<<x+1<<endl;
		}
		else{
			cout<<*st.find_by_order(1)+1<<endl;
		}
	}
}

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