| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1363513 | madamadam3 | Genetics (BOI18_genetics) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
/*
trying the bitset idea with the subtasks "dna has only A or C" worked for the smaller one, but failed
for the larger one until i cut the constant in half by only checking i+1..n, and precomputing counts for
those smaller than me. so now that its 4 bitsets not 1, maybe i can eliminate a bitset or 2 and also shuffling the order
means we expect to find the correct one within the first half of the array, halving the expected time
*/
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
vector<string> seq(n); for (int i = 0; i < n; i++) cin >> seq[i];
using b = bitset<4100>;
vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
shuffle(idx.begin(), idx.end(), rng);
vector<b> s1(n), s2(n);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
auto c = seq[idx[i]][j];
if (c == 'C' || c == 'T') s1[i][j] = 1;
if (c == 'G' || c == 'T') s2[i][j] = 1;
}
vector<int> cnt(n);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
int t = 0;
t += ((s1[i] ^ s1[j]) | (s2[i] ^ s2[j])).count();
if (t == k) cnt[i]++, cnt[j]++;
}
if (cnt[i] == n-1) {
cout << idx[i]+1 << "\n";
break;
}
}
return 0;
}