#include "dna.h"
#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
string sa, sb, a, b;
vector<int> acuma1,acuma2,acumt1,acumt2,acumc1,acumc2;
vector<int> AC, AT, CA, CT, TA, TC, SA, SC, ST;
void init(string a, string b) {
sa = a;
sb = b;
// Construimos la tabla de acumuladas
acuma1.assign(a.size(),0);
acumt1.assign(a.size(),0);
acumc1.assign(a.size(),0);
acuma2.assign(a.size(),0);
acumt2.assign(a.size(),0);
acumc2.assign(a.size(),0);
for(int i=0;i<a.size();i++){
// Acum A para el string 1
if(a[i]=='A') acuma1[i]++;
if(i>0) acuma1[i]+=acuma1[i-1];
// Acum A para el string 2
if(b[i]=='A'){
acuma2[i]++;
SA.push_back(i);
}
if(i>0) acuma2[i]+=acuma2[i-1];
// Acum T para el string 1
if(a[i]=='T') acumt1[i]++;
if(i>0) acumt1[i]+=acumt1[i-1];
// Acum T para el string 2
if(b[i]=='T'){
acumt2[i]++;
ST.push_back(i);
}
if(i>0) acumt2[i]+=acumt2[i-1];
// Acum C para el string 1
if(a[i]=='C') acumc1[i]++;
if(i>0) acumc1[i]+=acumc1[i-1];
// Acum C para el string 2
if(b[i]=='C'){
acumc2[i]++;
SC.push_back(i);
}
if(i>0) acumc2[i]+=acumc2[i-1];
// Preproceso
if(a[i]=='A' and b[i]=='C') AC.push_back(i);
if(a[i]=='A' and b[i]=='T') AT.push_back(i);
if(a[i]=='C' and b[i]=='A') CA.push_back(i);
if(a[i]=='C' and b[i]=='T') CT.push_back(i);
if(a[i]=='T' and b[i]=='A') TA.push_back(i);
if(a[i]=='T' and b[i]=='C') TC.push_back(i);
}
}
bool posible_transformar(int x, int y){
int ca1 = acuma1[y];
if(x>0) ca1 -= acuma1[x-1];
int ca2 = acuma2[y];
if(x>0) ca2 -= acuma2[x-1];
int cc1 = acumc1[y];
if(x>0) cc1 -= acumc1[x-1];
int cc2 = acumc2[y];
if(x>0) cc2 -= acumc2[x-1];
int ct1 = acumt1[y];
if(x>0) ct1 -= acumt1[x-1];
int ct2 = acumt2[y];
if(x>0) ct2 -= acumt2[x-1];
return (ca1==ca2 and cc1 == cc2 and ct1 == ct2);
}
int get_distance(int x, int y) {
int res = 0;
a = sa;
b = sb;
// SUBTASK 1,2 y 4
vector<int>::iterator it;
int pos;
//cout<<"Caso "<<x<<" "<<y<<"\n";
if(posible_transformar(x,y)){
for(int i=x;i<=y;i++){ // O(n)
if(a[i]==b[i]) continue;
else{
res++;
if(a[i]=='A' and b[i]=='C'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(CA.begin(),CA.end(),i);
if(it!=CA.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==CA.end()) break;
pos = *it;
}
if(it!=CA.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(SA.begin(),SA.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==SA.end()) break;
pos = *it;
}
if(it!=SA.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
if(a[i]=='A' and b[i]=='T'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(TA.begin(),TA.end(),i);
if(it!=TA.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==TA.end()) break;
pos = *it;
}
if(it!=TA.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(SA.begin(),SA.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==SA.end()) break;
pos = *it;
}
if(it!=SA.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
if(a[i]=='C' and b[i]=='A'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(AC.begin(),AC.end(),i);
if(it!=AC.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==AC.end()) break;
pos = *it;
}
if(it!=AC.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(SC.begin(),SC.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==SC.end()) break;
pos = *it;
}
if(it!=SC.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
if(a[i]=='C' and b[i]=='T'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(TC.begin(),TC.end(),i);
if(it!=TC.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==TC.end()) break;
pos = *it;
}
if(it!=TC.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(SC.begin(),SC.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==SC.end()) break;
pos = *it;
}
if(it!=SC.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
if(a[i]=='T' and b[i]=='A'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(AT.begin(),AT.end(),i);
if(it!=AT.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==AT.end()) break;
pos = *it;
}
if(it!=AT.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(ST.begin(),ST.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==ST.end()) break;
pos = *it;
}
if(it!=ST.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
if(a[i]=='T' and b[i]=='C'){
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(CT.begin(),CT.end(),i);
if(it!=CT.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==CT.end()) break;
pos = *it;
}
if(it!=CT.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
// Buscar cualquier letra que sirva
it = upper_bound(ST.begin(),ST.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==ST.end()) break;
pos = *it;
}
if(it!=ST.end() and pos<=y){
swap(b[i],b[pos]);
continue;
}
}
}
}
return res;
}
else return -1;
}
