#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);
}
void cambio(char c1, char c2, int y, int i){
vector<int>::iterator it;
int pos;
vector<int> doble,simple;
// TO-DO quien es doble y simple
if(a[i]=='A' and b[i]=='C'){
doble = CA;
simple = SA;
}
if(a[i]=='A' and b[i]=='T'){
doble = TA;
simple = SA;
}
if(a[i]=='C' and b[i]=='A'){
doble = AC;
simple = SC;
}
if(a[i]=='C' and b[i]=='T'){
doble = TC;
simple = SC;
}
if(a[i]=='T' and b[i]=='A'){
doble = AT;
simple = ST;
}
if(a[i]=='T' and b[i]=='C'){
doble = CT;
simple = ST;
}
// Buscamos algo que mate dos pajaros de un tiro
it = upper_bound(doble.begin(),doble.end(),i);
if(it!=doble.end()){
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==doble.end()) break;
pos = *it;
}
if(it!=doble.end() and pos<=y){
swap(b[i],b[pos]);
return;
}
}
// Buscar cualquier A
it = upper_bound(simple.begin(),simple.end(),i);
pos = *it;
while(a[pos]==b[pos]){
it++;
if(it==simple.end()) break;
pos = *it;
}
if(it!=simple.end() and pos<=y){
swap(b[i],b[pos]);
return;
}
}
int get_distance(int x, int y) {
int res = 0;
a = sa;
b = sb;
// SUBTASK 1,2 y 4
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{
cambio(a[i],b[i],y,i);
cout<<"-----------\n";
cout<<a<<"\n";
cout<<b<<"\n";
res++;
}
}
return res;
}
else return -1;
}
