#include "dna.h"
using namespace std;
#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
const int N = 1e5 + 5;
int cnt[2][N][5];
int c[N][5][5];
void init(string a, string b) {
for(int i = 0; i < len(a); i++){
cnt[0][i + 1][0] = cnt[0][i][0] + (a[i] == 'A');
cnt[0][i + 1][1] = cnt[0][i][1] + (a[i] == 'C');
cnt[0][i + 1][2] = cnt[0][i][2] + (a[i] == 'T');
c[i + 1][0][1] = c[i][0][1] + (a[i] == 'A' && b[i] == 'C');
c[i + 1][0][2] = c[i][0][2] + (a[i] == 'A' && b[i] == 'T');
c[i + 1][1][0] = c[i][1][0] + (a[i] == 'C' && b[i] == 'A');
c[i + 1][1][2] = c[i][1][2] + (a[i] == 'C' && b[i] == 'T');
c[i + 1][2][0] = c[i][2][0] + (a[i] == 'T' && b[i] == 'A');
c[i + 1][2][1] = c[i][2][1] + (a[i] == 'T' && b[i] == 'C');
}
for(int i = 0; i < len(b); i++){
cnt[1][i + 1][0] = cnt[1][i][0] + (b[i] == 'A');
cnt[1][i + 1][1] = cnt[1][i][1] + (b[i] == 'C');
cnt[1][i + 1][2] = cnt[1][i][2] + (b[i] == 'T');
}
}
int get_distance(int x, int y) {
if(cnt[0][y + 1][0] - cnt[0][x][0] != cnt[1][y + 1][0] - cnt[1][x][0]) return -1;
if(cnt[0][y + 1][1] - cnt[0][x][1] != cnt[1][y + 1][1] - cnt[1][x][1]) return -1;
if(cnt[0][y + 1][2] - cnt[0][x][2] != cnt[1][y + 1][2] - cnt[1][x][2]) return -1;
int sum = 0, ret = 0, now;
sum += c[y + 1][0][1] + c[y + 1][0][2] + c[y + 1][1][0] + c[y + 1][1][2] + c[y + 1][2][0] + c[y + 1][2][1] - (c[x][0][1] + c[x][0][2] + c[x][1][0] + c[x][1][2] + c[x][2][0] + c[x][2][1]);
now = min(c[y + 1][0][1] - c[x][0][1], c[y + 1][1][0] - c[x][1][0]);
ret += now;
sum -= 2 * now;
now = min(c[y + 1][0][2] - c[x][0][2], c[y + 1][2][0] - c[x][2][0]);
ret += now;
sum -= 2 * now;
now = min(c[y + 1][2][1] - c[x][2][1], c[y + 1][1][2] - c[x][1][2]);
ret += now;
sum -= 2 * now;
ret += (sum / 3) * 2;
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
16980 KB |
Output is correct |
2 |
Correct |
54 ms |
17128 KB |
Output is correct |
3 |
Correct |
48 ms |
15888 KB |
Output is correct |
4 |
Correct |
50 ms |
17152 KB |
Output is correct |
5 |
Correct |
0 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
10 ms |
14512 KB |
Output is correct |
5 |
Correct |
9 ms |
14720 KB |
Output is correct |
6 |
Correct |
10 ms |
14636 KB |
Output is correct |
7 |
Correct |
10 ms |
13692 KB |
Output is correct |
8 |
Correct |
11 ms |
14764 KB |
Output is correct |
9 |
Correct |
10 ms |
14768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
10 ms |
14512 KB |
Output is correct |
5 |
Correct |
9 ms |
14720 KB |
Output is correct |
6 |
Correct |
10 ms |
14636 KB |
Output is correct |
7 |
Correct |
10 ms |
13692 KB |
Output is correct |
8 |
Correct |
11 ms |
14764 KB |
Output is correct |
9 |
Correct |
10 ms |
14768 KB |
Output is correct |
10 |
Correct |
50 ms |
16996 KB |
Output is correct |
11 |
Correct |
53 ms |
17116 KB |
Output is correct |
12 |
Correct |
46 ms |
16472 KB |
Output is correct |
13 |
Correct |
64 ms |
16872 KB |
Output is correct |
14 |
Correct |
55 ms |
17536 KB |
Output is correct |
15 |
Correct |
57 ms |
17416 KB |
Output is correct |
16 |
Correct |
39 ms |
16424 KB |
Output is correct |
17 |
Correct |
44 ms |
16788 KB |
Output is correct |
18 |
Correct |
54 ms |
17444 KB |
Output is correct |
19 |
Correct |
38 ms |
16456 KB |
Output is correct |
20 |
Correct |
46 ms |
16800 KB |
Output is correct |
21 |
Correct |
48 ms |
17512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
10 ms |
14512 KB |
Output is correct |
5 |
Correct |
9 ms |
14720 KB |
Output is correct |
6 |
Correct |
10 ms |
14636 KB |
Output is correct |
7 |
Correct |
10 ms |
13692 KB |
Output is correct |
8 |
Correct |
11 ms |
14764 KB |
Output is correct |
9 |
Correct |
10 ms |
14768 KB |
Output is correct |
10 |
Correct |
11 ms |
13508 KB |
Output is correct |
11 |
Correct |
10 ms |
14764 KB |
Output is correct |
12 |
Correct |
10 ms |
13724 KB |
Output is correct |
13 |
Correct |
13 ms |
14676 KB |
Output is correct |
14 |
Correct |
9 ms |
14676 KB |
Output is correct |
15 |
Correct |
9 ms |
14676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
16980 KB |
Output is correct |
2 |
Correct |
54 ms |
17128 KB |
Output is correct |
3 |
Correct |
48 ms |
15888 KB |
Output is correct |
4 |
Correct |
50 ms |
17152 KB |
Output is correct |
5 |
Correct |
0 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
10 ms |
14512 KB |
Output is correct |
12 |
Correct |
9 ms |
14720 KB |
Output is correct |
13 |
Correct |
10 ms |
14636 KB |
Output is correct |
14 |
Correct |
10 ms |
13692 KB |
Output is correct |
15 |
Correct |
11 ms |
14764 KB |
Output is correct |
16 |
Correct |
10 ms |
14768 KB |
Output is correct |
17 |
Correct |
50 ms |
16996 KB |
Output is correct |
18 |
Correct |
53 ms |
17116 KB |
Output is correct |
19 |
Correct |
46 ms |
16472 KB |
Output is correct |
20 |
Correct |
64 ms |
16872 KB |
Output is correct |
21 |
Correct |
55 ms |
17536 KB |
Output is correct |
22 |
Correct |
57 ms |
17416 KB |
Output is correct |
23 |
Correct |
39 ms |
16424 KB |
Output is correct |
24 |
Correct |
44 ms |
16788 KB |
Output is correct |
25 |
Correct |
54 ms |
17444 KB |
Output is correct |
26 |
Correct |
38 ms |
16456 KB |
Output is correct |
27 |
Correct |
46 ms |
16800 KB |
Output is correct |
28 |
Correct |
48 ms |
17512 KB |
Output is correct |
29 |
Correct |
11 ms |
13508 KB |
Output is correct |
30 |
Correct |
10 ms |
14764 KB |
Output is correct |
31 |
Correct |
10 ms |
13724 KB |
Output is correct |
32 |
Correct |
13 ms |
14676 KB |
Output is correct |
33 |
Correct |
9 ms |
14676 KB |
Output is correct |
34 |
Correct |
9 ms |
14676 KB |
Output is correct |
35 |
Correct |
1 ms |
296 KB |
Output is correct |
36 |
Correct |
58 ms |
15948 KB |
Output is correct |
37 |
Correct |
65 ms |
17304 KB |
Output is correct |
38 |
Correct |
52 ms |
16728 KB |
Output is correct |
39 |
Correct |
52 ms |
17524 KB |
Output is correct |
40 |
Correct |
55 ms |
17560 KB |
Output is correct |
41 |
Correct |
9 ms |
14752 KB |
Output is correct |
42 |
Correct |
43 ms |
16616 KB |
Output is correct |
43 |
Correct |
60 ms |
17500 KB |
Output is correct |
44 |
Correct |
51 ms |
17420 KB |
Output is correct |
45 |
Correct |
58 ms |
16636 KB |
Output is correct |
46 |
Correct |
39 ms |
17484 KB |
Output is correct |
47 |
Correct |
53 ms |
17432 KB |
Output is correct |