# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1042455 | vjudge1 | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
vector<long long> at, ac, ca, ct, ta, tc;
void init(string a,string b)
{
int n = a.size() + 1;
a = '#' + a;
b = '#' + b;
at.resize(n + 1, 0);
ac.resize(n + 1, 0);
ca.resize(n + 1, 0);
ct.resize(n + 1, 0);
ta.resize(n + 1, 0);
tc.resize(n + 1, 0);
for(int i = 1; i <= n; ++i)
{
if(a[i] == 'A')
{
if(b[i] == 'C')
ac[i] = ac[i - 1] + 1;
if(b[i] == 'T')
at[i] = at[i - 1] + 1;
}
if(a[i] == 'T')
{
if(b[i] == 'A')
ta[i] = ta[i - 1] + 1;
if(b[i] == 'C')
tc[i] = tc[i - 1] + 1;
}
if(a[i] == 'C')
{
if(b[i] == 'A')
ca[i] = ca[i - 1] + 1;
if(b[i] == 'T')
ct[i] = ct[i - 1] + 1;
}
}
}
int get_distance(int x, int y)
{
int acc = (ac[y + 1] - ac[x]);
int att = (at[y + 1] - at[x]);
int ctt = (ct[y + 1] - ct[x]);
int caa = (ca[y + 1] - ca[x]);
int tcc = (tc[y + 1] - tc[x]);
int taa = (ta[y + 1] - ta[x]);
if(acc + att != taa + caa) {return -1;}
if(caa + ctt != acc + tcc) {return -1;}
if(taa + tcc != att + ctt) {return -1;}
int mn1 = min(acc,caa), mn2 = min(att,taa), mn3 = min(tcc,ctt);
ans += mn1 + mn2 + mn3;
acc -= mn1;
caa -= mn1;
att -= mn2;
taa -= mn2;
tcc -= mn3;
ctt -= mn3;
int sum = max({att, taa, ctt, tcc, acc, caa});
ans += sum * 2;
return ans;
}