#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int mxN = 2e5 + 1000;
string A, B;
int dp[mxN][10];
void init(string a, string b){
A = a, B = b;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= (int) a.size(); ++i){
for(int j = 0; j <= 9; ++j) dp[i][j] = dp[i - 1][j];
dp[i][0] += A[i] == 'A';
dp[i][0] -= B[i] == 'A';
dp[i][1] += A[i] == 'C';
dp[i][1] -= B[i] == 'C';
dp[i][2] += A[i] == 'T';
dp[i][2] -= B[i] == 'T';
dp[i][3] += A[i] == 'A' && B[i] == 'T';
dp[i][4] += A[i] == 'T' && B[i] == 'A';
dp[i][5] += A[i] == 'A' && B[i] == 'C';
dp[i][6] += A[i] == 'C' && B[i] == 'A';
dp[i][7] += A[i] == 'T' && B[i] == 'C';
dp[i][8] += A[i] == 'C' && B[i] == 'T';
dp[i][9] += A[i] == B[i];
}
}
int get(int x, int y, int t){
return dp[y][t] - dp[x - 1][t];
}
int get_distance(int x, int y){
++y, ++x;
int a = get(x, y, 0), c = get(x, y, 1), t = get(x, y, 2), good = get(x, y, 9),
at = get(x, y, 3), ta = get(x, y, 4), ac = get(x, y, 5), ca = get(x, y, 6), tc = get(x, y, 7), ct = get(x, y, 8);
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), one = 1, moves = 0;
while(hehehe > 0){
if(one == 1) --hehehe;
else hehehe -= 2;
one = 1 - one;
++moves;
}
return min(at, ta) + min(ac, ca) + min(tc, ct) + moves;
}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;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |