# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1236965 | i_love_mriti | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int mxN = 2e5 + 1000;
string A, B;
void init(string a, string b){
A = a, B = b;
}
int get_distance(int x, int y){
int a = 0, c = 0, t = 0, good = 0, at = 0, ta = 0, ac = 0, ca = 0, tc = 0, ct = 0;
for(int i = x; i <= y; ++i){
a += A[i] == 'A';
a -= B[i] == 'A';
c += A[i] == 'C';
c -= B[i] == 'C';
t += A[i] == 'T';
t -= B[i] == 'T';
if(A[i] == 'A' && B[i] == 'T') ++at;
else if(A[i] == 'T' && B[i] == 'A') ++ta;
else if(A[i] == 'A' && B[i] == 'C') ++ac;
else if(A[i] == 'C' && B[i] == 'A') ++ca;
else if(A[i] == 'C' && B[i] == 'T') ++ct;
else if(A[i] == 'T' && B[i] == 'C') ++tc;
else ++good;
}
if(a == 0 && c == 0 && t == 0){
if(good == (y - x + 1)) return 0;
int hehehe = ((y - x + 1) - min(at, ta) * 2 - min(ac, ca) * 2 - min(tc, ct) * 2 - good);
return min(at, ta) + min(ac, ca) + min(tc, ct) + (hehehe + 1) / 2;
}else{
return -1;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("inp.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
init("ACTCAT", "TACACT");
cout << get_distance(0, 5) << endl;
return 0;
}