#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l,int r) { return uniform_int_distribution<int>(l,r)(rng); }
const int MAXN=4114;
bitset<MAXN> bt[MAXN][4];
bool ck[MAXN],cs[MAXN][MAXN];
int get(int x,int y)
{
return (bt[x][0]&bt[y][0]).count()+(bt[x][1]&bt[y][1]).count()+(bt[x][2]&bt[y][2]).count()+(bt[x][3]&bt[y][3]).count();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
int cnt=n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='A') bt[i][0][j]=1;
if(s[j]=='C') bt[i][1][j]=1;
if(s[j]=='G') bt[i][2][j]=1;
if(s[j]=='T') bt[i][3][j]=1;
}
}
k=m-k;
for(int i=1;i<=n;i++) cs[i][i]=true;
while(cnt>1)
{
int l=Rand(1,n),r=Rand(1,n);
while(cs[l][r]) l=Rand(1,n),r=Rand(1,n);
cs[l][r]=cs[r][l]=true;
if(get(l,r)!=k)
{
if(!ck[l]) ck[l]=true,cnt--;
if(!ck[r]) ck[r]=true,cnt--;
}
}
for(int i=1;i<=n;i++) if(!ck[i]) return cout<<i,0;
}
# | 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... |