#include <bits/stdc++.h>
#define nl '\n'
#define pb push_back
#define ll long long
#define VMAX 100001
#define NMAX 35005
#define INF 10000000000000000
using namespace std;
string A,B;
int n,p=0;
int cod[256];
int prefixsum[4][4][100005],aux[4][4];
void init(string a,string b)
{
A=a;
B=b;
n=a.size();
cod['A']=1;
cod['C']=2;
cod['T']=3;
for(int k1=1;k1<=3;k1++)
{
for(int k2=1;k2<=3;k2++)
{
for(int i=0;i<n;i++)
{
if(i==0)
{
prefixsum[k1][k2][i]=0;
}
else
{
prefixsum[k1][k2][i]=prefixsum[k1][k2][i-1];
}
if(cod[A[i]]==k1&&cod[B[i]]==k2)
{
prefixsum[k1][k2][i]++;
}
}
}
}
}
int get_distance(int x,int y)
{
int ans=y-x+1,cycles=0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
aux[i][j]=prefixsum[i][j][y];
if(x)
{
aux[i][j]-=prefixsum[i][j][x-1];
}
}
}
for(int i=1;i<=3;i++)
{
cycles+=aux[i][i];
aux[i][i]=0;
}
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
int p=min(aux[i][j],aux[j][i]);
aux[i][j]-=p;
aux[j][i]-=p;
cycles+=p;
}
}
///mai avem doar cycluri de lungime 3
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
if(i!=j&&i!=k&&j!=k)
{
int p=min(min(aux[i][j],aux[j][k]),aux[k][i]);
cycles+=p;
aux[i][j]-=p;
aux[j][k]-=p;
aux[k][i]-=p;
p=min(min(aux[i][k],aux[j][i]),aux[k][j]);
aux[i][k]-=p;
aux[j][i]-=p;
aux[k][j]-=p;
cycles+=p;
}
}
}
}
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
if(aux[i][j]) return -1;
}
}
return ans-cycles;
}
/*
int main()
{
int N, q;
assert(scanf("%d %d", &N, &q) == 2);
char X[n+1], Y[n+1];
assert(scanf("%s", X) == 1);
assert(scanf("%s", Y) == 1);
std::string a = std::string(X);
std::string b = std::string(Y);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}
Compilation message
dna.cpp:105:1: error: unterminated comment
105 | /*
| ^
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:36:28: warning: array subscript has type 'char' [-Wchar-subscripts]
36 | if(cod[A[i]]==k1&&cod[B[i]]==k2)
| ^
dna.cpp:36:43: warning: array subscript has type 'char' [-Wchar-subscripts]
36 | if(cod[A[i]]==k1&&cod[B[i]]==k2)
| ^
