| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 437250 | irmuun | 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<bits/stdc++.h>
#include "dna.h"
using namespace std;
string A,B;
int p[100001][3][3],i,c,d,e,f,g,j,k,h[3][3],ch[100001][3],ch1[100001][3],dif[2][3],ans;
void init(string a,string b){
for(i=0;i<3;i++){
ch[0][i]=0;
ch1[0][i]=0;
for(j=0;j<3;j++){
p[0][i][j]=0;
}
}
for(i=0;i<a.size();i++){
if(a[i]=='A'){
d=0;
}
else if(a[i]=='C'){
d=1;
}
else{
d=2;
}
if(b[i]=='A'){
e=0;
}
else if(b[i]=='C'){
e=1;
}
else{
e=2;
}
for(j=0;j<3;j++){
if(j==d){
ch[i+1][j]=ch[i][j]+1;
}
else{
ch[i+1][j]=ch[i][j];
}
if(j==e){
ch1[i+1][j]=ch1[i][j]+1;
}
else{
ch1[i+1][j]=ch1[i][j];
}
for(k=0;k<3;k++){
if(j==d&&k==e){
p[i+1][j][k]=p[i][j][k]+1;
}
else{
p[i+1][j][k]=p[i][j][k];
}
}
}
}
}
int get_distanse(int x,int y){
ans=0;
for(i=0;i<3;i++){
dif[0][0]=ch[y+1][0]-ch[x][0];
dif[0][1]=ch[y+1][1]-ch[x][1];
dif[0][2]=ch[y+1][2]-ch[x][2];
dif[1][0]=ch1[y+1][0]-ch1[x][0];
dif[1][1]=ch1[y+1][1]-ch1[x][1];
dif[1][2]=ch1[y+1][2]-ch1[x][2];
for(j=0;j<3;j++){
h[i][j]=p[y+1][i][j]-p[x][i][j];
}
}
if(dif[0][0]!=dif[1][0]||dif[0][1]!=dif[1][1]||dif[0][2]!=dif[1][2]){
return -1;
}
f=min(h[0][1],min(h[1][2],h[2][0]));
g=min(h[1][0],min(h[2][1],h[0][2]));
ans+=(f+g)*2;
h[0][1]-=f;
h[1][2]-=f;
h[2][0]-=f;
h[1][0]-=g;
h[2][1]-=g;
h[0][2]-=g;
return ans+h[0][1]+h[1][2]+h[2][0];
}