# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1251246 | FernandoJC07 | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define vi vector<int>
#define For(i, a, n) for(int i = a; i<n; ++i)
using namespace std;
unordered_map<char, int> ump;
vii ps;
int cod(int a, int b){ return a+3*b;}
pair<int, int> dec(int a){ return {a%3, a/3};}
int idec(int a) {return cod(dec(a).ss, dec(a).ff);}
void init(string a, string b){
int n = a.size();
ump['A'] = 0; ump['C'] = 1; ump['T'] = 2;
ps.resize(n+1, vi(9, 0));
For(i, 0, n){
ps[i+1] = ps[i];
ps[i+1][cod(ump[a[i]], ump[b[i]])]++;
}
}
int get_distance(int x, int y){
++x; ++y;
vi v(9);
For(i, 0, 9) v[i] = ps[y][i] - ps[x-1][i];
vi a(3, 0), b(3, 0);
For(i, 0, 9){
auto s = dec(i);
a[s.ff] += v[i]; b[s.ss] += v[i];
}
if(a != b) return -1;
int n = y-x+1;
int t = n - v[0] - v[4] - v[8];
int p = 0; For(i, 0, 9) p += min(v[i], v[idec(i)]);
int ans = (4*t - p)/6;
return ans;
}