#include <string>
#include <iostream>
using namespace std;
const int maxN = 100005;
int n, v1[maxN], v2[maxN], sp[maxN][10], sp1[maxN][3], sp2[maxN][3];
int getCode(char c) {
if (c == 'A') {
return 0;
}
if (c == 'C') {
return 1;
}
if (c == 'T') {
return 2;
}
}
void initString(string s, int v[], int sp[maxN][3]) {
for (int i = 1; i <= n; i++) {
v[i] = getCode(s[i - 1]);
for (int j = 0; j < 3; j++) {
sp[i][j] = sp[i - 1][j];
}
sp[i][v[i]]++;
}
}
void init(string a, string b) {
n = (int) a.size();
initString(a, v1, sp1);
initString(b, v2, sp2);
for (int i = 1; i <= n; i++) {
int code = v1[i] * 3 + v2[i];
for (int j = 0; j < 9; j++) {
sp[i][j] = sp[i - 1][j];
}
sp[i][code]++;
}
}
/// AC = 1
/// AT = 2
/// CA = 3
/// CT = 5
/// TA = 6
/// TC = 7
int get_distance(int x, int y) {
y++;
for (int j = 0; j < 3; j++) {
if ((sp1[y][j] - sp1[x][j]) != (sp2[y][j] - sp2[x][j])) {
return -1;
}
}
int AC = sp[y][1] - sp[x][1];
int AT = sp[y][2] - sp[x][2];
int CA = sp[y][3] - sp[x][3];
int CT = sp[y][5] - sp[x][5];
int TA = sp[y][6] - sp[x][6];
int TC = sp[y][7] - sp[x][7];
int min1 = min(AC, CA), min2 = min(AT, TA), min3 = min(CT, TC);
int ans = min1 + min2 + min3;
AC -= min1; CA -= min1;
AT -= min2; TA -= min2;
CT -= min3; TC -= min3;
ans += 2 * (AC + CA);
return ans;
}
Compilation message
dna.cpp: In function 'int getCode(char)':
dna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
19 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
9296 KB |
Output is correct |
2 |
Correct |
26 ms |
9296 KB |
Output is correct |
3 |
Correct |
26 ms |
9168 KB |
Output is correct |
4 |
Correct |
27 ms |
10668 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
4 ms |
8028 KB |
Output is correct |
5 |
Correct |
4 ms |
8024 KB |
Output is correct |
6 |
Correct |
4 ms |
8024 KB |
Output is correct |
7 |
Correct |
4 ms |
8024 KB |
Output is correct |
8 |
Correct |
5 ms |
8024 KB |
Output is correct |
9 |
Correct |
4 ms |
8024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
4 ms |
8028 KB |
Output is correct |
5 |
Correct |
4 ms |
8024 KB |
Output is correct |
6 |
Correct |
4 ms |
8024 KB |
Output is correct |
7 |
Correct |
4 ms |
8024 KB |
Output is correct |
8 |
Correct |
5 ms |
8024 KB |
Output is correct |
9 |
Correct |
4 ms |
8024 KB |
Output is correct |
10 |
Correct |
27 ms |
9308 KB |
Output is correct |
11 |
Correct |
27 ms |
9308 KB |
Output is correct |
12 |
Correct |
27 ms |
9416 KB |
Output is correct |
13 |
Correct |
28 ms |
9400 KB |
Output is correct |
14 |
Correct |
30 ms |
9656 KB |
Output is correct |
15 |
Correct |
27 ms |
9444 KB |
Output is correct |
16 |
Correct |
26 ms |
9412 KB |
Output is correct |
17 |
Correct |
27 ms |
9400 KB |
Output is correct |
18 |
Correct |
27 ms |
9644 KB |
Output is correct |
19 |
Correct |
27 ms |
9416 KB |
Output is correct |
20 |
Correct |
26 ms |
9664 KB |
Output is correct |
21 |
Correct |
27 ms |
9652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2392 KB |
Output is correct |
4 |
Correct |
4 ms |
8028 KB |
Output is correct |
5 |
Correct |
4 ms |
8024 KB |
Output is correct |
6 |
Correct |
4 ms |
8024 KB |
Output is correct |
7 |
Correct |
4 ms |
8024 KB |
Output is correct |
8 |
Correct |
5 ms |
8024 KB |
Output is correct |
9 |
Correct |
4 ms |
8024 KB |
Output is correct |
10 |
Correct |
4 ms |
7768 KB |
Output is correct |
11 |
Correct |
4 ms |
8280 KB |
Output is correct |
12 |
Correct |
4 ms |
8024 KB |
Output is correct |
13 |
Correct |
4 ms |
8280 KB |
Output is correct |
14 |
Correct |
5 ms |
8280 KB |
Output is correct |
15 |
Correct |
4 ms |
8280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
9296 KB |
Output is correct |
2 |
Correct |
26 ms |
9296 KB |
Output is correct |
3 |
Correct |
26 ms |
9168 KB |
Output is correct |
4 |
Correct |
27 ms |
10668 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
2392 KB |
Output is correct |
11 |
Correct |
4 ms |
8028 KB |
Output is correct |
12 |
Correct |
4 ms |
8024 KB |
Output is correct |
13 |
Correct |
4 ms |
8024 KB |
Output is correct |
14 |
Correct |
4 ms |
8024 KB |
Output is correct |
15 |
Correct |
5 ms |
8024 KB |
Output is correct |
16 |
Correct |
4 ms |
8024 KB |
Output is correct |
17 |
Correct |
27 ms |
9308 KB |
Output is correct |
18 |
Correct |
27 ms |
9308 KB |
Output is correct |
19 |
Correct |
27 ms |
9416 KB |
Output is correct |
20 |
Correct |
28 ms |
9400 KB |
Output is correct |
21 |
Correct |
30 ms |
9656 KB |
Output is correct |
22 |
Correct |
27 ms |
9444 KB |
Output is correct |
23 |
Correct |
26 ms |
9412 KB |
Output is correct |
24 |
Correct |
27 ms |
9400 KB |
Output is correct |
25 |
Correct |
27 ms |
9644 KB |
Output is correct |
26 |
Correct |
27 ms |
9416 KB |
Output is correct |
27 |
Correct |
26 ms |
9664 KB |
Output is correct |
28 |
Correct |
27 ms |
9652 KB |
Output is correct |
29 |
Correct |
4 ms |
7768 KB |
Output is correct |
30 |
Correct |
4 ms |
8280 KB |
Output is correct |
31 |
Correct |
4 ms |
8024 KB |
Output is correct |
32 |
Correct |
4 ms |
8280 KB |
Output is correct |
33 |
Correct |
5 ms |
8280 KB |
Output is correct |
34 |
Correct |
4 ms |
8280 KB |
Output is correct |
35 |
Correct |
1 ms |
2392 KB |
Output is correct |
36 |
Correct |
32 ms |
10392 KB |
Output is correct |
37 |
Correct |
27 ms |
10668 KB |
Output is correct |
38 |
Correct |
28 ms |
10904 KB |
Output is correct |
39 |
Correct |
28 ms |
10988 KB |
Output is correct |
40 |
Correct |
28 ms |
10928 KB |
Output is correct |
41 |
Correct |
4 ms |
8280 KB |
Output is correct |
42 |
Correct |
27 ms |
10688 KB |
Output is correct |
43 |
Correct |
27 ms |
10924 KB |
Output is correct |
44 |
Correct |
27 ms |
10924 KB |
Output is correct |
45 |
Correct |
27 ms |
10684 KB |
Output is correct |
46 |
Correct |
26 ms |
10924 KB |
Output is correct |
47 |
Correct |
27 ms |
10932 KB |
Output is correct |