| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 985435 | user736482 | 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>
using namespace std;
vector<int>pref[9];//a a t t c c a t t a t c c t c a a c
void init(string a,string b){
for(int i=0;i<9;i++)
pref[i].push_back(0);
for(iny i=0;i<(int)a.size();i++){
pref[0].push_back(pref[0][i]);
pref[1].push_back(pref[1][i]);
pref[2].push_back(pref[2][i]);
pref[3].push_back(pref[3][i]);
pref[4].push_back(pref[4][i]);
pref[5].push_back(pref[5][i]);
pref[6].push_back(pref[6][i]);
pref[7].push_back(pref[7][i]);
pref[8].push_back(pref[8][i]);
if(a[i]=='A' && b[i]=='A')
pref[0][i+1]++;
if(a[i]=='T' && b[i]=='T')
pref[1][i+1]++;
if(a[i]=='C' && b[i]=='C')
pref[2][i+1]++;
if(a[i]=='A' && b[i]=='T')
pref[3][i+1]++;
if(a[i]=='T' && b[i]=='A')
pref[4][i+1]++;
if(a[i]=='T' && b[i]=='C')
pref[5][i+1]++;
if(a[i]=='C' && b[i]=='T')
pref[6][i+1]++;
if(a[i]=='C' && b[i]=='A')
pref[7][i+1]++;
if(a[i]=='A' && b[i]=='C')
pref[8][i+1]++;
}}
int get_distance(int x,int y){
int answer=0;
int dist=y-x+1;
dist-=(pref[0][y+1]-pref[0][x]);
dist-=(pref[1][y+1]-pref[1][x]);
dist-=(pref[2][y+1]-pref[2][x]);
dist-=2*min((pref[3][y+1]-pref[3][x]),(pref[4][y+1]-pref[4][x]));
answer+=min((pref[3][y+1]-pref[3][x]),(pref[4][y+1]-pref[4][x]));
dist-=2*min((pref[5][y+1]-pref[5][x]),(pref[6][y+1]-pref[6][x]));
answer+=min((pref[5][y+1]-pref[5][x]),(pref[6][y+1]-pref[6][x]));
dist-=2*min((pref[7][y+1]-pref[7][x]),(pref[8][y+1]-pref[8][x]));
answer+=min((pref[7][y+1]-pref[7][x]),(pref[8][y+1]-pref[8][x]));
answer+=dist*2/3;
return answer;
}