#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 10;
int Aa[MX], Ab[MX], Ca[MX], Cb[MX], Ta[MX], Tb[MX], AC[MX], CA[MX], AT[MX], TA[MX], TC[MX], CT[MX];
void init(std::string a, std::string b)
{
int n = a.size();
for (int i = 0; i < n; i++)
{
Aa[i + 1] += Aa[i];
Ca[i + 1] += Ca[i];
Ta[i + 1] += Ta[i];
Ab[i + 1] += Ab[i];
Cb[i + 1] += Cb[i];
Tb[i + 1] += Tb[i];
AC[i + 1] += AC[i];
AT[i + 1] += AT[i];
CA[i + 1] += CA[i];
TA[i + 1] += TA[i];
CT[i + 1] += CT[i];
TC[i + 1] += TC[i];
char x = a[i], y = b[i];
if (x == 'A')
Aa[i + 1]++;
if (x == 'C')
Ca[i + 1]++;
if (x == 'T')
Ta[i + 1]++;
if (y == 'A')
Ab[i + 1]++;
if (y == 'C')
Cb[i + 1]++;
if (y == 'T')
Tb[i + 1]++;
if (x == 'A' && y == 'C')
AC[i + 1]++;
if (x == 'A' && y == 'T')
AT[i + 1]++;
if (x == 'C' && y == 'A')
CA[i + 1]++;
if (x == 'C' && y == 'T')
CT[i + 1]++;
if (x == 'T' && y == 'A')
TA[i + 1]++;
if (x == 'T' && y == 'C')
TC[i + 1]++;
}
}
int get_distance(int x, int y)
{
x++, y++;
if(Aa[y] - Aa[x - 1] != Ab[y] - Ab[x - 1])
return -1;
if(Ca[y] - Ca[x - 1] != Cb[y] - Cb[x - 1])
return -1;
if(Ta[y] - Ta[x - 1] != Tb[y] - Tb[x - 1])
return -1;
int a = AC[y] - AC[x - 1];
int b = CA[y] - CA[x - 1];
int c = AT[y] - AT[x - 1];
int d = TA[y] - TA[x - 1];
int e = CT[y] - CT[x - 1];
int f = TC[y] - TC[x - 1];
if(a > b)
swap(a, b);
if(c > d)
swap(c, d);
if(e > f)
swap(e, f);
return a + c + e + (((b - a) + (d - c) + (f - e)) / 3) * 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
8172 KB |
Output is correct |
2 |
Correct |
38 ms |
8224 KB |
Output is correct |
3 |
Correct |
33 ms |
7776 KB |
Output is correct |
4 |
Correct |
36 ms |
8200 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
6 ms |
5688 KB |
Output is correct |
5 |
Correct |
7 ms |
5696 KB |
Output is correct |
6 |
Correct |
7 ms |
5716 KB |
Output is correct |
7 |
Correct |
6 ms |
5440 KB |
Output is correct |
8 |
Correct |
7 ms |
5728 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
6 ms |
5688 KB |
Output is correct |
5 |
Correct |
7 ms |
5696 KB |
Output is correct |
6 |
Correct |
7 ms |
5716 KB |
Output is correct |
7 |
Correct |
6 ms |
5440 KB |
Output is correct |
8 |
Correct |
7 ms |
5728 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
39 ms |
8136 KB |
Output is correct |
11 |
Correct |
40 ms |
8184 KB |
Output is correct |
12 |
Correct |
46 ms |
8196 KB |
Output is correct |
13 |
Correct |
35 ms |
8308 KB |
Output is correct |
14 |
Correct |
43 ms |
8568 KB |
Output is correct |
15 |
Correct |
36 ms |
8488 KB |
Output is correct |
16 |
Correct |
36 ms |
8148 KB |
Output is correct |
17 |
Correct |
38 ms |
8304 KB |
Output is correct |
18 |
Correct |
51 ms |
8468 KB |
Output is correct |
19 |
Correct |
48 ms |
8168 KB |
Output is correct |
20 |
Correct |
31 ms |
8212 KB |
Output is correct |
21 |
Correct |
31 ms |
8440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
6 ms |
5688 KB |
Output is correct |
5 |
Correct |
7 ms |
5696 KB |
Output is correct |
6 |
Correct |
7 ms |
5716 KB |
Output is correct |
7 |
Correct |
6 ms |
5440 KB |
Output is correct |
8 |
Correct |
7 ms |
5728 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
7 ms |
5336 KB |
Output is correct |
11 |
Correct |
7 ms |
5744 KB |
Output is correct |
12 |
Correct |
7 ms |
5416 KB |
Output is correct |
13 |
Correct |
9 ms |
5688 KB |
Output is correct |
14 |
Correct |
8 ms |
5716 KB |
Output is correct |
15 |
Correct |
8 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
8172 KB |
Output is correct |
2 |
Correct |
38 ms |
8224 KB |
Output is correct |
3 |
Correct |
33 ms |
7776 KB |
Output is correct |
4 |
Correct |
36 ms |
8200 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
6 ms |
5688 KB |
Output is correct |
12 |
Correct |
7 ms |
5696 KB |
Output is correct |
13 |
Correct |
7 ms |
5716 KB |
Output is correct |
14 |
Correct |
6 ms |
5440 KB |
Output is correct |
15 |
Correct |
7 ms |
5728 KB |
Output is correct |
16 |
Correct |
5 ms |
5716 KB |
Output is correct |
17 |
Correct |
39 ms |
8136 KB |
Output is correct |
18 |
Correct |
40 ms |
8184 KB |
Output is correct |
19 |
Correct |
46 ms |
8196 KB |
Output is correct |
20 |
Correct |
35 ms |
8308 KB |
Output is correct |
21 |
Correct |
43 ms |
8568 KB |
Output is correct |
22 |
Correct |
36 ms |
8488 KB |
Output is correct |
23 |
Correct |
36 ms |
8148 KB |
Output is correct |
24 |
Correct |
38 ms |
8304 KB |
Output is correct |
25 |
Correct |
51 ms |
8468 KB |
Output is correct |
26 |
Correct |
48 ms |
8168 KB |
Output is correct |
27 |
Correct |
31 ms |
8212 KB |
Output is correct |
28 |
Correct |
31 ms |
8440 KB |
Output is correct |
29 |
Correct |
7 ms |
5336 KB |
Output is correct |
30 |
Correct |
7 ms |
5744 KB |
Output is correct |
31 |
Correct |
7 ms |
5416 KB |
Output is correct |
32 |
Correct |
9 ms |
5688 KB |
Output is correct |
33 |
Correct |
8 ms |
5716 KB |
Output is correct |
34 |
Correct |
8 ms |
5716 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
38 ms |
7672 KB |
Output is correct |
37 |
Correct |
49 ms |
8200 KB |
Output is correct |
38 |
Correct |
35 ms |
8212 KB |
Output is correct |
39 |
Correct |
40 ms |
8560 KB |
Output is correct |
40 |
Correct |
45 ms |
8584 KB |
Output is correct |
41 |
Correct |
6 ms |
5716 KB |
Output is correct |
42 |
Correct |
33 ms |
8180 KB |
Output is correct |
43 |
Correct |
36 ms |
8432 KB |
Output is correct |
44 |
Correct |
35 ms |
8436 KB |
Output is correct |
45 |
Correct |
43 ms |
8164 KB |
Output is correct |
46 |
Correct |
46 ms |
8492 KB |
Output is correct |
47 |
Correct |
31 ms |
8524 KB |
Output is correct |