#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int mp[205], cnta[mxn][5], cntb[mxn][5], mutate[mxn][5][5];
void init(string a, string b) {
mp['A'] = 0, mp['T'] = 1, mp['C'] = 2;
a = " " + a, b = " " + b;
for (int i = 1; i < a.length(); i++) {
for (int j = 0; j < 3; j++) {
cnta[i][j] = cnta[i - 1][j];
cntb[i][j] = cntb[i - 1][j];
for (int k = 0; k < 3; k++) mutate[i][j][k] = mutate[i - 1][j][k];
}
cnta[i][mp[a[i]]]++;
cntb[i][mp[b[i]]]++;
if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
}
}
int get_distance(int x, int y) {
y++;
for (int i = 0; i < 3; i++) if (cnta[y][i] - cnta[x][i] != cntb[y][i] - cntb[x][i]) return -1;
int a = mutate[y][0][1] - mutate[x][0][1];
int b = mutate[y][1][0] - mutate[x][1][0];
int c = mutate[y][0][2] - mutate[x][0][2];
int d = mutate[y][2][0] - mutate[x][2][0];
int e = mutate[y][1][2] - mutate[x][1][2];
int f = mutate[y][2][1] - mutate[x][2][1];
return min(a, b) + min(c, d) + min(e, f) + (abs(a - b) + abs(c - d) + abs(e - f)) * 2 / 3;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 1; i < a.length(); i++) {
| ~~^~~~~~~~~~~~
dna.cpp:18:24: warning: array subscript has type 'char' [-Wchar-subscripts]
18 | cnta[i][mp[a[i]]]++;
| ^
dna.cpp:19:24: warning: array subscript has type 'char' [-Wchar-subscripts]
19 | cntb[i][mp[b[i]]]++;
| ^
dna.cpp:20:44: warning: array subscript has type 'char' [-Wchar-subscripts]
20 | if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
| ^
dna.cpp:20:54: warning: array subscript has type 'char' [-Wchar-subscripts]
20 | if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
17100 KB |
Output is correct |
2 |
Correct |
48 ms |
17248 KB |
Output is correct |
3 |
Correct |
41 ms |
15908 KB |
Output is correct |
4 |
Correct |
42 ms |
17264 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
9 ms |
14804 KB |
Output is correct |
5 |
Correct |
9 ms |
14932 KB |
Output is correct |
6 |
Correct |
10 ms |
14804 KB |
Output is correct |
7 |
Correct |
9 ms |
13892 KB |
Output is correct |
8 |
Correct |
9 ms |
14912 KB |
Output is correct |
9 |
Correct |
10 ms |
14892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
9 ms |
14804 KB |
Output is correct |
5 |
Correct |
9 ms |
14932 KB |
Output is correct |
6 |
Correct |
10 ms |
14804 KB |
Output is correct |
7 |
Correct |
9 ms |
13892 KB |
Output is correct |
8 |
Correct |
9 ms |
14912 KB |
Output is correct |
9 |
Correct |
10 ms |
14892 KB |
Output is correct |
10 |
Correct |
43 ms |
17020 KB |
Output is correct |
11 |
Correct |
41 ms |
17280 KB |
Output is correct |
12 |
Correct |
41 ms |
16484 KB |
Output is correct |
13 |
Correct |
41 ms |
16956 KB |
Output is correct |
14 |
Correct |
41 ms |
17548 KB |
Output is correct |
15 |
Correct |
55 ms |
17476 KB |
Output is correct |
16 |
Correct |
39 ms |
16476 KB |
Output is correct |
17 |
Correct |
39 ms |
16824 KB |
Output is correct |
18 |
Correct |
38 ms |
17464 KB |
Output is correct |
19 |
Correct |
34 ms |
16456 KB |
Output is correct |
20 |
Correct |
35 ms |
16832 KB |
Output is correct |
21 |
Correct |
34 ms |
17476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
9 ms |
14804 KB |
Output is correct |
5 |
Correct |
9 ms |
14932 KB |
Output is correct |
6 |
Correct |
10 ms |
14804 KB |
Output is correct |
7 |
Correct |
9 ms |
13892 KB |
Output is correct |
8 |
Correct |
9 ms |
14912 KB |
Output is correct |
9 |
Correct |
10 ms |
14892 KB |
Output is correct |
10 |
Correct |
8 ms |
13632 KB |
Output is correct |
11 |
Correct |
11 ms |
14908 KB |
Output is correct |
12 |
Correct |
8 ms |
14016 KB |
Output is correct |
13 |
Correct |
10 ms |
14788 KB |
Output is correct |
14 |
Correct |
9 ms |
14932 KB |
Output is correct |
15 |
Correct |
11 ms |
14948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
17100 KB |
Output is correct |
2 |
Correct |
48 ms |
17248 KB |
Output is correct |
3 |
Correct |
41 ms |
15908 KB |
Output is correct |
4 |
Correct |
42 ms |
17264 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
9 ms |
14804 KB |
Output is correct |
12 |
Correct |
9 ms |
14932 KB |
Output is correct |
13 |
Correct |
10 ms |
14804 KB |
Output is correct |
14 |
Correct |
9 ms |
13892 KB |
Output is correct |
15 |
Correct |
9 ms |
14912 KB |
Output is correct |
16 |
Correct |
10 ms |
14892 KB |
Output is correct |
17 |
Correct |
43 ms |
17020 KB |
Output is correct |
18 |
Correct |
41 ms |
17280 KB |
Output is correct |
19 |
Correct |
41 ms |
16484 KB |
Output is correct |
20 |
Correct |
41 ms |
16956 KB |
Output is correct |
21 |
Correct |
41 ms |
17548 KB |
Output is correct |
22 |
Correct |
55 ms |
17476 KB |
Output is correct |
23 |
Correct |
39 ms |
16476 KB |
Output is correct |
24 |
Correct |
39 ms |
16824 KB |
Output is correct |
25 |
Correct |
38 ms |
17464 KB |
Output is correct |
26 |
Correct |
34 ms |
16456 KB |
Output is correct |
27 |
Correct |
35 ms |
16832 KB |
Output is correct |
28 |
Correct |
34 ms |
17476 KB |
Output is correct |
29 |
Correct |
8 ms |
13632 KB |
Output is correct |
30 |
Correct |
11 ms |
14908 KB |
Output is correct |
31 |
Correct |
8 ms |
14016 KB |
Output is correct |
32 |
Correct |
10 ms |
14788 KB |
Output is correct |
33 |
Correct |
9 ms |
14932 KB |
Output is correct |
34 |
Correct |
11 ms |
14948 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
41 ms |
15964 KB |
Output is correct |
37 |
Correct |
42 ms |
17224 KB |
Output is correct |
38 |
Correct |
41 ms |
16700 KB |
Output is correct |
39 |
Correct |
42 ms |
17552 KB |
Output is correct |
40 |
Correct |
45 ms |
17588 KB |
Output is correct |
41 |
Correct |
9 ms |
14932 KB |
Output is correct |
42 |
Correct |
47 ms |
16560 KB |
Output is correct |
43 |
Correct |
39 ms |
17500 KB |
Output is correct |
44 |
Correct |
39 ms |
17476 KB |
Output is correct |
45 |
Correct |
34 ms |
16644 KB |
Output is correct |
46 |
Correct |
38 ms |
17520 KB |
Output is correct |
47 |
Correct |
37 ms |
17476 KB |
Output is correct |