#include <bits/stdc++.h>
using namespace std;
int dtoi(char c) {
if (c == 'A')
return 0;
if (c == 'G')
return 1;
if (c == 'C')
return 2;
if (c == 'T')
return 3;
exit(-1);
}
char itod(int x) {
return "AGCT"[x];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<string> C(n);
vector<vector<int>> cnt(m, vector<int>(4));
for (string &s : C) {
cin >> s;
for (int i = 0; i < m; i++)
cnt[i][dtoi(s[i])]++;
}
random_device rd;
mt19937_64 g(rd());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), g);
auto ok = [&](int i) {
for (int j : p) {
if (j == i)
continue;
int s = 0;
for (int l = 0; s <= k && l < m; l++) {
s += (C[i][l] != C[j][l]);
}
if (s != k)
return false;
}
return true;
};
for (int i : p) {
int s = 0;
for (int j = 0; s <= (n - 1) * k && j < m; j++) {
for (int l = 0; l < 4; l++) {
if (l != dtoi(C[i][j]))
s += cnt[j][l];
}
}
if (s > (n - 1) * k)
continue;
if (ok(i)) {
cout << i + 1;
return 0;
}
}
cout << -1;
}
# | 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... |