# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1108243 | Newtonabc | 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 "dna.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int prea[N],preb[N],pre[N];
string tmpa,tmpb;
void init(std::string a, std::string b) {
int n=a.size();
tmpa=a,tmpb=b;
prea[0]=(a[0]=='A'),preb[0]=(b[0]=='A');
for(int i=1;i<n;i++) prea[i]=prea[i-1]+(a[i]=='A'),preb[i]=preb[i-1]+(b[i]=='A');
pre[0]=(a[0]!=b[0]);
for(int i=1;i<n;i++) pre[i]=pre[i-1]+(a[i]!=b[i]);
/*for(int i=0;i<n;i++) cout<<pre[i] <<" ";
cout<<'\n';*/
}
int get_distance(int x, int y) {
if(y-x<=2){
int aa=0,at=0,ag=0,ba=0,bt=0,bg=0;
for(int i=x;i<=y;i++){
if(tmpa[i]=='A') aa++;
if(tmpa[i]=='T') at++;
if(tmpa[i]=='G') ag++;
if(tmpb[i]=='A') ba++;
if(tmpb[i]=='T') bt++;
if(tmpb[i]=='G') bg++;
}
if((aa==ba && at==bt && ag==bg)==0) return -1;
bool b=true;
for(int i=x;i<=y;i++) if(a[i]!=b[i]) b=false;
if(!b) return 0;
int cnt=0;
for(int i=x;i<=y;i++) if(a[i]!=b[i]) cnt++;
if(cnt==3) return 2;
else return 1;
}
if(prea[y]-(x-1>=0?prea[x-1]:0)==preb[y]-(x-1>=0?preb[x-1]:0)) return (pre[y]-(x-1>=0?pre[x-1]:0))/2;
return -1;
}