#include "dna.h"
#include <bits/stdc++.h>
int N;
int *anumA, *anumT, *anumC;
int *bnumA, *bnumT, *bnumC;
int *diff;
int *dats, *dacs, *dtas, *dtcs, *dcas, *dcts;
std::string A, B;
void init(std::string _a, std::string _b) {
A = std::move(_a);
B = std::move(_b);
N = A.size();
for (auto x: {&anumA, &anumT, &anumC, &bnumA, &bnumT, &bnumC, &diff, &dats, &dacs, &dtas, &dtcs, &dcas, &dcts}) {
*x = new int[N];
}
anumA[0] = A[0] == 'A';
anumT[0] = A[0] == 'T';
anumC[0] = A[0] == 'C';
bnumA[0] = B[0] == 'A';
bnumT[0] = B[0] == 'T';
bnumC[0] = B[0] == 'C';
diff[0] = A[0] != B[0];
dats[0] = (A[0] == 'A' && B[0] == 'T');
dacs[0] = (A[0] == 'A' && B[0] == 'C');
dtas[0] = (A[0] == 'T' && B[0] == 'A');
dtcs[0] = (A[0] == 'T' && B[0] == 'C');
dcas[0] = (A[0] == 'C' && B[0] == 'A');
dcts[0] = (A[0] == 'C' && B[0] == 'T');
for (int i = 1; i < N; ++i) {
anumA[i] = anumA[i - 1] + (A[i] == 'A');
anumT[i] = anumT[i - 1] + (A[i] == 'T');
anumC[i] = anumC[i - 1] + (A[i] == 'C');
bnumA[i] = bnumA[i - 1] + (B[i] == 'A');
bnumT[i] = bnumT[i - 1] + (B[i] == 'T');
bnumC[i] = bnumC[i - 1] + (B[i] == 'C');
diff[i] = diff[i - 1] + (A[i] != B[i]);
dats[i] = dats[i - 1] + (A[i] == 'A' && B[i] == 'T');
dacs[i] = dacs[i - 1] + (A[i] == 'A' && B[i] == 'C');
dtas[i] = dtas[i - 1] + (A[i] == 'T' && B[i] == 'A');
dtcs[i] = dtcs[i - 1] + (A[i] == 'T' && B[i] == 'C');
dcas[i] = dcas[i - 1] + (A[i] == 'C' && B[i] == 'A');
dcts[i] = dcts[i - 1] + (A[i] == 'C' && B[i] == 'T');
}
}
int num(int *data, int l, int r) {
int x = data[r];
if (l) x -= data[l - 1];
return x;
}
int get_distance(int x, int y) {
int aa = num(anumA, x, y);
int ba = num(bnumA, x, y);
int at = num(anumT, x, y);
int bt = num(bnumT, x, y);
int ac = num(anumC, x, y);
int bc = num(bnumC, x, y);
if (aa != ba || at != bt || ac != bc) return -1;
if (y - x <= 2) {//Subtask 1
int d = 0;
for (int i = x; i <= y; ++i) {
d += A[i] != B[i];
}
return (d + 1) / 2;
}
if ((ac == 0 && bc == 0) || (aa == 0 && ba == 0) || (at == 0 && bt == 0)) {
return num(diff, x, y) / 2;
}
int dac = num(dacs, x, y);
int dat = num(dats, x, y);
int dta = num(dtas, x, y);
int dtc = num(dtcs, x, y);
int dca = num(dcas, x, y);
int dct = num(dcts, x, y);
int groupA = dac - dca;
assert(groupA == dta - dat);
assert(groupA == dct - dtc);
int ans = 0;
if (groupA > 0) {
ans = 2 * groupA;
dac -= groupA;
dct -= groupA;
dta -= groupA;
} else if (groupA < 0) {
ans = -2 * groupA;
dca += groupA;
dtc += groupA;
dat += groupA;
}
assert(dac == dca);
assert(dat == dta);
assert(dct == dtc);
ans += dac + dat + dct;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
7248 KB |
Output is correct |
2 |
Correct |
36 ms |
7260 KB |
Output is correct |
3 |
Correct |
34 ms |
7000 KB |
Output is correct |
4 |
Correct |
41 ms |
7244 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
13 ms |
5980 KB |
Output is correct |
5 |
Correct |
13 ms |
5916 KB |
Output is correct |
6 |
Correct |
14 ms |
5980 KB |
Output is correct |
7 |
Correct |
14 ms |
5724 KB |
Output is correct |
8 |
Correct |
13 ms |
5980 KB |
Output is correct |
9 |
Correct |
13 ms |
5980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
13 ms |
5980 KB |
Output is correct |
5 |
Correct |
13 ms |
5916 KB |
Output is correct |
6 |
Correct |
14 ms |
5980 KB |
Output is correct |
7 |
Correct |
14 ms |
5724 KB |
Output is correct |
8 |
Correct |
13 ms |
5980 KB |
Output is correct |
9 |
Correct |
13 ms |
5980 KB |
Output is correct |
10 |
Correct |
35 ms |
7256 KB |
Output is correct |
11 |
Correct |
36 ms |
7248 KB |
Output is correct |
12 |
Correct |
36 ms |
7248 KB |
Output is correct |
13 |
Correct |
41 ms |
7508 KB |
Output is correct |
14 |
Correct |
37 ms |
7772 KB |
Output is correct |
15 |
Correct |
36 ms |
7600 KB |
Output is correct |
16 |
Correct |
36 ms |
7356 KB |
Output is correct |
17 |
Correct |
35 ms |
7508 KB |
Output is correct |
18 |
Correct |
40 ms |
7780 KB |
Output is correct |
19 |
Correct |
34 ms |
7260 KB |
Output is correct |
20 |
Correct |
34 ms |
7512 KB |
Output is correct |
21 |
Correct |
36 ms |
7764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
13 ms |
5980 KB |
Output is correct |
5 |
Correct |
13 ms |
5916 KB |
Output is correct |
6 |
Correct |
14 ms |
5980 KB |
Output is correct |
7 |
Correct |
14 ms |
5724 KB |
Output is correct |
8 |
Correct |
13 ms |
5980 KB |
Output is correct |
9 |
Correct |
13 ms |
5980 KB |
Output is correct |
10 |
Correct |
12 ms |
5468 KB |
Output is correct |
11 |
Correct |
14 ms |
5980 KB |
Output is correct |
12 |
Correct |
12 ms |
5724 KB |
Output is correct |
13 |
Correct |
14 ms |
6016 KB |
Output is correct |
14 |
Correct |
14 ms |
5980 KB |
Output is correct |
15 |
Correct |
13 ms |
6224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
7248 KB |
Output is correct |
2 |
Correct |
36 ms |
7260 KB |
Output is correct |
3 |
Correct |
34 ms |
7000 KB |
Output is correct |
4 |
Correct |
41 ms |
7244 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
13 ms |
5980 KB |
Output is correct |
12 |
Correct |
13 ms |
5916 KB |
Output is correct |
13 |
Correct |
14 ms |
5980 KB |
Output is correct |
14 |
Correct |
14 ms |
5724 KB |
Output is correct |
15 |
Correct |
13 ms |
5980 KB |
Output is correct |
16 |
Correct |
13 ms |
5980 KB |
Output is correct |
17 |
Correct |
35 ms |
7256 KB |
Output is correct |
18 |
Correct |
36 ms |
7248 KB |
Output is correct |
19 |
Correct |
36 ms |
7248 KB |
Output is correct |
20 |
Correct |
41 ms |
7508 KB |
Output is correct |
21 |
Correct |
37 ms |
7772 KB |
Output is correct |
22 |
Correct |
36 ms |
7600 KB |
Output is correct |
23 |
Correct |
36 ms |
7356 KB |
Output is correct |
24 |
Correct |
35 ms |
7508 KB |
Output is correct |
25 |
Correct |
40 ms |
7780 KB |
Output is correct |
26 |
Correct |
34 ms |
7260 KB |
Output is correct |
27 |
Correct |
34 ms |
7512 KB |
Output is correct |
28 |
Correct |
36 ms |
7764 KB |
Output is correct |
29 |
Correct |
12 ms |
5468 KB |
Output is correct |
30 |
Correct |
14 ms |
5980 KB |
Output is correct |
31 |
Correct |
12 ms |
5724 KB |
Output is correct |
32 |
Correct |
14 ms |
6016 KB |
Output is correct |
33 |
Correct |
14 ms |
5980 KB |
Output is correct |
34 |
Correct |
13 ms |
6224 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
35 ms |
7300 KB |
Output is correct |
37 |
Correct |
36 ms |
7808 KB |
Output is correct |
38 |
Correct |
38 ms |
7508 KB |
Output is correct |
39 |
Correct |
42 ms |
8580 KB |
Output is correct |
40 |
Correct |
40 ms |
8528 KB |
Output is correct |
41 |
Correct |
14 ms |
6132 KB |
Output is correct |
42 |
Correct |
43 ms |
7612 KB |
Output is correct |
43 |
Correct |
38 ms |
8232 KB |
Output is correct |
44 |
Correct |
43 ms |
8276 KB |
Output is correct |
45 |
Correct |
36 ms |
8124 KB |
Output is correct |
46 |
Correct |
44 ms |
8376 KB |
Output is correct |
47 |
Correct |
37 ms |
8024 KB |
Output is correct |