# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1212317 | StefanSebez | Genetics (BOI18_genetics) | C++20 | 2058 ms | 31180 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
#pragma GCC target("popcnt")
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;
}
bitset<N>bt[4][N];
int GET(int i,int j){
int res=0;
for(int k=0;k<4;k++){
res+=(bt[k][i]&bt[k][j]).count();
}
return m-res;
}
int main(){
scanf("%i%i%i",&n,&m,&K);
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]=='A') bt[0][i][j]=1;
if(s[i][j]=='C') bt[1][i][j]=1;
if(s[i][j]=='G') bt[2][i][j]=1;
if(s[i][j]=='T') bt[3][i][j]=1;
}
}
/*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;
}
if(ind.size()==1) break;
}*/
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
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... |