| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1122594 | I_FloPPed21 | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <iostream>
using namespace std;
const int N=1e5+5;
int sp_a[N],sp_b[N];
int a1[N],b1[N],c1[N];
int a2[N],b2[N],c2[N];
int difs[N][5][5];
int get_distance(int x,int y)
{
x++,y++;
if((a1[y]-a1[x-1])!=(a2[y]-a2[x-1]))
return -1;
if((b1[y]-b1[x-1])!=(b2[y]-b2[x-1]))
return -1;
if((c1[y]-c1[x-1])!=(c2[y]-c2[x-1]))
return -1;
int rem=0;
int sp=0,ans=0;
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
int cost1=difs[y][i][j]-difs[x-1][i][j];
int cost2=difs[y][j][i]-difs[x-1][j][i];
ans+=min(cost1,cost2);
sp+=abs(cost1-cost2);
}
}
return ans+(sp)/3*2;
}
void init(string a,string b)
{
a="#"+a;
b="#"+b;
int d=a.size();
for(int i=1; i<=d; i++)
{
a1[i]+=a1[i-1];
a2[i]+=a2[i-1];
b1[i]+=b1[i-1];
b2[i]+=b2[i-1];
c1[i]+=c1[i-1];
c2[i]+=c2[i-1];
if(a[i]=='A')
a1[i]++;
if(a[i]=='C')
b1[i]++;
if(a[i]=='T')
c1[i]++;
if(b[i]=='A')
a2[i]++;
if(b[i]=='C')
b2[i]++;
if(b[i]=='T')
c2[i]++;
for(int j=1; j<=3; j++)
for(int k=1; k<=3; k++)
difs[i][j][k]+=difs[i-1][j][k];
if(a[i]!=b[i])
{
int cons1=0,cons2=0;
if(a[i]=='A')
cons1=1;
else if(a[i]=='C')
cons1=2;
else
cons1=3;
if(b[i]=='A')
cons2=1;
else if(b[i]=='C')
cons2=2;
else
cons2=3;
difs[i][cons1][cons2]++;
}
}
}
int main()
{
init("ATACAT","ACTATA");
cout<<difs[5][1][3]-difs[3][1][3]<<'\n';
cout<<get_distance(3,5)<<'\n';
return 0;
}