#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int prefA[N][3], prefB[N][3];
int pref[N][3][3];
void init(string a, string b) {
int n = a.size();
int arrA[n + 1], arrB[n + 1];
for(int i = 0; i < a.size(); i++) {
arrA[i + 1] = ((a[i] == 'A') ? 0 : ((a[i] == 'C') ? 1 : 2));
arrB[i + 1] = ((b[i] == 'A') ? 0 : ((b[i] == 'C') ? 1 : 2));
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < 3; j++) {
prefA[i][j] = 0;
prefB[i][j] = 0;
for(int k = 0; k < 3; k++) {
pref[i][j][k] = 0;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) {
prefA[i][j] = prefA[i - 1][j];
prefB[i][j] = prefB[i - 1][j];
for(int k = 0; k < 3; k++) {
pref[i][j][k] = pref[i - 1][j][k];
}
}
prefA[i][arrA[i]]++;
prefB[i][arrB[i]]++;
pref[i][arrA[i]][arrB[i]]++;
}
}
int get_distance(int x, int y) {
x++, y++;
if((prefA[y][0] - prefA[x - 1][0] != prefB[y][0] - prefB[x - 1][0]) || (prefA[y][1] - prefA[x - 1][1] != prefB[y][1] - prefB[x - 1][1]) || (prefA[y][2] - prefA[x - 1][2] != prefB[y][2] - prefB[x - 1][2])) {
return -1;
}
int res = 0;
int ans[3] = {0, 0, 0};
int carry[3] = {0, 0, 0};
ans[0] += min(pref[y][0][1] - pref[x - 1][0][1], pref[y][1][0] - pref[x - 1][1][0]);
ans[1] += min(pref[y][0][2] - pref[x - 1][0][2], pref[y][2][0] - pref[x - 1][2][0]);
ans[2] += min(pref[y][1][2] - pref[x - 1][1][2], pref[y][2][1] - pref[x - 1][2][1]);
//cout << "ans[0] = " << ans[0] << ", ans[1] = " << ans[1] << ", ans[2] = " << ans[2] << "\n";
int sum = ans[0] + ans[1] + ans[2];
res = sum;
int left = y - x + 1 - sum * 2;
left -= (pref[y][0][0] - pref[x - 1][0][0] + pref[y][1][1] - pref[x - 1][1][1] + pref[y][2][2] - pref[x - 1][2][2]);
//cout << "left = " << left << ", x = " << x << ", y = " << y << "\n";
assert(left % 3 == 0);
res += (left / 3) * 2;
return res;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:19: 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 = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:46:6: warning: unused variable 'carry' [-Wunused-variable]
46 | int carry[3] = {0, 0, 0};
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
8764 KB |
Output is correct |
2 |
Correct |
46 ms |
8820 KB |
Output is correct |
3 |
Correct |
42 ms |
8684 KB |
Output is correct |
4 |
Correct |
61 ms |
8832 KB |
Output is correct |
5 |
Correct |
4 ms |
6092 KB |
Output is correct |
6 |
Correct |
5 ms |
6092 KB |
Output is correct |
7 |
Correct |
4 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6060 KB |
Output is correct |
2 |
Correct |
4 ms |
6084 KB |
Output is correct |
3 |
Correct |
4 ms |
6092 KB |
Output is correct |
4 |
Correct |
8 ms |
7500 KB |
Output is correct |
5 |
Correct |
8 ms |
7500 KB |
Output is correct |
6 |
Correct |
8 ms |
7520 KB |
Output is correct |
7 |
Correct |
9 ms |
7420 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6060 KB |
Output is correct |
2 |
Correct |
4 ms |
6084 KB |
Output is correct |
3 |
Correct |
4 ms |
6092 KB |
Output is correct |
4 |
Correct |
8 ms |
7500 KB |
Output is correct |
5 |
Correct |
8 ms |
7500 KB |
Output is correct |
6 |
Correct |
8 ms |
7520 KB |
Output is correct |
7 |
Correct |
9 ms |
7420 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
10 |
Correct |
46 ms |
8704 KB |
Output is correct |
11 |
Correct |
45 ms |
8708 KB |
Output is correct |
12 |
Correct |
46 ms |
8976 KB |
Output is correct |
13 |
Correct |
47 ms |
9100 KB |
Output is correct |
14 |
Correct |
47 ms |
9140 KB |
Output is correct |
15 |
Correct |
59 ms |
9012 KB |
Output is correct |
16 |
Correct |
42 ms |
9072 KB |
Output is correct |
17 |
Correct |
44 ms |
9080 KB |
Output is correct |
18 |
Correct |
43 ms |
9088 KB |
Output is correct |
19 |
Correct |
40 ms |
9104 KB |
Output is correct |
20 |
Correct |
39 ms |
9100 KB |
Output is correct |
21 |
Correct |
41 ms |
9212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6060 KB |
Output is correct |
2 |
Correct |
4 ms |
6084 KB |
Output is correct |
3 |
Correct |
4 ms |
6092 KB |
Output is correct |
4 |
Correct |
8 ms |
7500 KB |
Output is correct |
5 |
Correct |
8 ms |
7500 KB |
Output is correct |
6 |
Correct |
8 ms |
7520 KB |
Output is correct |
7 |
Correct |
9 ms |
7420 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
10 |
Correct |
8 ms |
7372 KB |
Output is correct |
11 |
Correct |
8 ms |
7500 KB |
Output is correct |
12 |
Correct |
8 ms |
7444 KB |
Output is correct |
13 |
Correct |
8 ms |
7500 KB |
Output is correct |
14 |
Correct |
8 ms |
7500 KB |
Output is correct |
15 |
Correct |
7 ms |
7500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
8764 KB |
Output is correct |
2 |
Correct |
46 ms |
8820 KB |
Output is correct |
3 |
Correct |
42 ms |
8684 KB |
Output is correct |
4 |
Correct |
61 ms |
8832 KB |
Output is correct |
5 |
Correct |
4 ms |
6092 KB |
Output is correct |
6 |
Correct |
5 ms |
6092 KB |
Output is correct |
7 |
Correct |
4 ms |
6092 KB |
Output is correct |
8 |
Correct |
4 ms |
6060 KB |
Output is correct |
9 |
Correct |
4 ms |
6084 KB |
Output is correct |
10 |
Correct |
4 ms |
6092 KB |
Output is correct |
11 |
Correct |
8 ms |
7500 KB |
Output is correct |
12 |
Correct |
8 ms |
7500 KB |
Output is correct |
13 |
Correct |
8 ms |
7520 KB |
Output is correct |
14 |
Correct |
9 ms |
7420 KB |
Output is correct |
15 |
Correct |
9 ms |
7424 KB |
Output is correct |
16 |
Correct |
9 ms |
7500 KB |
Output is correct |
17 |
Correct |
46 ms |
8704 KB |
Output is correct |
18 |
Correct |
45 ms |
8708 KB |
Output is correct |
19 |
Correct |
46 ms |
8976 KB |
Output is correct |
20 |
Correct |
47 ms |
9100 KB |
Output is correct |
21 |
Correct |
47 ms |
9140 KB |
Output is correct |
22 |
Correct |
59 ms |
9012 KB |
Output is correct |
23 |
Correct |
42 ms |
9072 KB |
Output is correct |
24 |
Correct |
44 ms |
9080 KB |
Output is correct |
25 |
Correct |
43 ms |
9088 KB |
Output is correct |
26 |
Correct |
40 ms |
9104 KB |
Output is correct |
27 |
Correct |
39 ms |
9100 KB |
Output is correct |
28 |
Correct |
41 ms |
9212 KB |
Output is correct |
29 |
Correct |
8 ms |
7372 KB |
Output is correct |
30 |
Correct |
8 ms |
7500 KB |
Output is correct |
31 |
Correct |
8 ms |
7444 KB |
Output is correct |
32 |
Correct |
8 ms |
7500 KB |
Output is correct |
33 |
Correct |
8 ms |
7500 KB |
Output is correct |
34 |
Correct |
7 ms |
7500 KB |
Output is correct |
35 |
Correct |
4 ms |
6068 KB |
Output is correct |
36 |
Correct |
55 ms |
8724 KB |
Output is correct |
37 |
Correct |
47 ms |
8704 KB |
Output is correct |
38 |
Correct |
46 ms |
9100 KB |
Output is correct |
39 |
Correct |
47 ms |
9084 KB |
Output is correct |
40 |
Correct |
46 ms |
9128 KB |
Output is correct |
41 |
Correct |
8 ms |
7500 KB |
Output is correct |
42 |
Correct |
55 ms |
9080 KB |
Output is correct |
43 |
Correct |
43 ms |
9136 KB |
Output is correct |
44 |
Correct |
43 ms |
9088 KB |
Output is correct |
45 |
Correct |
39 ms |
9076 KB |
Output is correct |
46 |
Correct |
43 ms |
9208 KB |
Output is correct |
47 |
Correct |
52 ms |
9156 KB |
Output is correct |