#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dna.h"
using namespace std;
const int maxn = 1e5 + 5;
int p1[maxn][3];
int p2[maxn][3];
int p3[maxn][3][3];
int s1[maxn];
int s2[maxn];
void init(string a, string b) {
memset(p1, 0, sizeof(p1));
memset(p2, 0, sizeof(p2));
memset(p3, 0, sizeof(p3));
for (int i = 0; i < a.size(); i++) {
if (a[i] == 'A')
s1[i] = 0;
else if (a[i] == 'C')
s1[i] = 1;
else
s1[i] = 2;
if (b[i] == 'A')
s2[i] = 0;
else if (b[i] == 'C')
s2[i] = 1;
else
s2[i] = 2;
}
p1[0][s1[0]]++;
p2[0][s2[0]]++;
p3[0][s1[0]][s2[0]]++;
for (int i = 1; i < a.size(); i++) {
for (int t1 = 0; t1 <= 2; t1++) {
for (int t2 = 0; t2 <= 2; t2++) {
p3[i][t1][t2] = p3[i - 1][t1][t2];
}
p1[i][t1] = p1[i - 1][t1];
p2[i][t1] = p2[i - 1][t1];
}
p3[i][s1[i]][s2[i]]++;
p1[i][s1[i]]++;
p2[i][s2[i]]++;
}
}
int c[3][3];
int get_distance(int x, int y) {
if (x == 0) {
if (p1[y][0] != p2[y][0] || p1[y][1] != p2[y][1] || p1[y][2] != p2[y][2]) {
return -1;
}
} else {
if (p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] ||
p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] ||
p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2]) {
return -1;
}
}
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
if (x == 0)
c[i][j] = p3[y][i][j];
else
c[i][j] = p3[y][i][j] - p3[x - 1][i][j];
}
}
int ans = 0;
int all = y - x + 1;
all -= c[0][0];
all -= c[1][1];
all -= c[2][2];
int h = min(c[0][1], c[1][0]);
ans += h;
all -=2* h;
h = min(c[0][2], c[2][0]);
ans += h;
all -=2* h;
h = min(c[1][2], c[2][1]);
ans += h;
all -=2* h;
ans += (all / 3) * 2;
return ans;
}
# | 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... |