# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1212316 | StefanSebez | Genetics (BOI18_genetics) | C++20 | 2093 ms | 23732 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=4110;
mt19937 rng(time(0));
int n,m,K;
string s[N];
bool was[N];
int dist[N][N];
int Get(int i,int j){
if(dist[i][j]) return dist[i][j];
int res=0;
for(int k=0;k<m;k++) if(s[i][k]!=s[j][k]) res++;
return dist[i][j]=res;
}
int main(){
scanf("%i%i%i",&n,&m,&K);
for(int i=0;i<n;i++) cin>>s[i];
for(int ct=1;ct<=n;ct++){
vector<int>temp;
for(int i=0;i<n;i++) temp.pb(i);
shuffle(temp.begin(),temp.end(),rng);
vector<int>ind;
bool broke=false;
for(auto i:temp){
if(!was[i]){
for(auto j:ind){
if(Get(i,j)!=K){
was[i]=was[j]=true;
broke=true;
}
}
ind.pb(i);
}
if(broke) break;
}
}
for(int i=0;i<n;i++){
if(was[i]) continue;
for(int j=0;j<n;j++){
if(i==j) continue;
if(Get(i,j)!=K) was[i]=was[j]=true;
}
}
int res=0;
for(int i=0;i<n;i++) if(!was[i]) res=i;
res++;
printf("%i\n",res);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |