# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1257670 | chikien2009 | Genetics (BOI18_genetics) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, m, k, id[5000], a, b, c;
long long sum[5000][4], all, temp;
mt19937 random(time(0));
string s[5000], t = "ATGC";
int main()
{
setup();
cin >> n >> m >> k;
for (int i = 0; i < n; ++i)
{
cin >> s[i];
id[i] = random() % ((int)1e9 + 7);
all += id[i];
for (int j = 0; j < m; ++j)
{
for (int c = 0; c < 4; ++c)
{
sum[j][c] += (s[i][j] != t[c]) * id[i];
}
}
}
for (int i = 0; i < n; ++i)
{
temp = 0;
for (int j = 0; j < m; ++j)
{
for (int c = 0; c < 4; ++c)
{
temp += sum[j][c] * (s[i][j] == t[c]);
}
}
if (temp == (all - id[i]) * k)
{
cout << i + 1;
return 0;
}
}
return 0;
}