# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
437870 | aggrovector | 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 "dna.h"
#include <iostream>
#include <bits/stdc++.h>
int s[100005],ac[100005],ca[100005],at[100005],ta[100005],ct[100005],tc[100005],n,i,mac,mat,mct;
void init(std::string a, std::string b) {
n=a.length();
for (i=0;i<n;i++) {
if (i==0) {
ac[i]=0;
ca[i]=0;
at[i]=0;
ta[i]=0;
ct[i]=0;
tc[i]=0;
}
else {
ac[i]=ac[i-1];
ca[i]=ca[i-1];
at[i]=at[i-1];
ta[i]=ta[i-1];
ct[i]=ct[i-1];
tc[i]=tc[i-1];
}
if (a[i]=='A') {
if (b[i]=='C') {
ac[i]++;
}
else if (b[i]=='T') {
at[i]++;
}
}
else if (a[i]=='C') {
if (b[i]=='A') {
ca[i]++;
}
else if (b[i]=='T') {
ct[i]++;
}
}
else if (a[i]=='T') {
if (b[i]=='A') {
ta[i]++;
}
else if (b[i]=='C') {
tc[i]++;
}
}
}
}
int get_distance(int x, int y) {
if (ac[y]-ac[x-1]+at[y]-at[x-1]!=ca[y]-ca[x-1]+ta[y]-ta[x-1]) {
return -1;
}
if (ca[y]-ca[x-1]+ct[y]-ct[x-1]!=ac[y]-ac[x-1]+tc[y]-tc[x-1]) {
return -1;
}
if (ta[y]-ta[x-1]+tc[y]-tc[x-1]!=at[y]-at[x-1]+ct[y]-ct[x-1]) {
return -1;
}
mac=min(ac[y]-ac[x-1],ca[y]-ca[x-1]);
mat=min(at[y]-at[x-1],ta[y]-ta[x-1]);
mct=min(ct[y]-ct[x-1],tc[y]-tc[x-1]);
return mac+mat+mct+2*(max(ac[y]-ac[x-1],ca[y]-ca[x-1])-mac);
}