# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
699029 | NourWael | 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 <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
int n,q;
cin>>n>>q;
string f,s;
cin>>f>>s;
int difference=0;
int d[100001];
vector<vector<int>>numbersA(n+1,vector<int>(3));
vector<vector<int>>numbersB(n+1,vector<int>(3));
int aa=0;
int ta=0;
int ca=0;
int ab=0;
int tb=0;
int cb=0;
for(int i=0; i<f.size(); i++)
{
if(f[i]!=s[i])
{
difference++;
}
d[i]=difference;
if(f[i]=='A')
{
aa++;
}
else if (f[i]=='T')
{
ta++;
}
else if (f[i]=='C')
{
ca++;
}
numbersA[i][0]=aa;
numbersA[i][1]=ta;
numbersA[i][2]=ca;
if(s[i]=='A')
{
ab++;
}
else if (s[i]=='T')
{
tb++;
}
else if (s[i]=='C')
{
cb++;
}
numbersB[i][0]=ab;
numbersB[i][1]=tb;
numbersB[i][2]=cb;
}
while(q--)
{
int x,y;
cin>>x>>y;
int div=d[y];
int da1=numbersA[y][0];
int dt1=numbersA[y][1];
int dc1=numbersA[y][2];
int da2=numbersB[y][0];
int dt2=numbersB[y][1];
int dc2=numbersB[y][2];
if(x!=0)
{
div=d[y]-d[x-1];
da1-=numbersA[x-1][0];
dt1-=numbersA[x-1][1];
dc1-=numbersA[x-1][2];
da2-=numbersB[x-1][0];
dt2-=numbersB[x-1][1];
dc2-=numbersB[x-1][2];
}
if(da1==da2 && dt1==dt2 && dc1==dc2)
{
cout<<ceil((double)div/2)<<'\n';
}
else
{
cout<<-1<<'\n';
}
}
return 0;
}