#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int lim = 1e5 + 5;
int cnt[2][3][lim];
int pref[3][3][lim];
char av[] = {'A', 'C', 'T'};
void init(std::string a, std::string b) {
n = a.size();
// init count of c a t
// ac
// ca
// at
// ta
// tc
// ct
for(int i = 0; i < n; ++i) {
if(i != 0) {
for(int j = 0; j < 3; ++j)
for(int k = 0; k < 2; ++k)
cnt[k][j][i] = cnt[k][j][i - 1];
}
for(int j = 0; j < 3; ++j) {
if(av[j] == a[i])
++cnt[0][j][i];
if(av[j] == b[i])
++cnt[1][j][i];
}
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) {
if(i != 0)
pref[j][k][i] = pref[j][k][i - 1];
if(av[j] == a[i] && av[k] == b[i])
++pref[j][k][i];
}
}
}
}
int get_distance(int x, int y) {
vector<int> cura, curb;
for(int i = 0; i < 3; ++i) {
int tmp1 = cnt[0][i][y], tmp2 = cnt[1][i][y];
if(x != 0)
tmp1 -= cnt[0][i][x - 1], tmp2 -= cnt[1][i][x - 1];
cura.push_back(tmp1), curb.push_back(tmp2);
}
if(cura != curb)
return -1;
int cur[3][3];
memset(cur, 0, sizeof(cur));
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
int tmp = pref[i][j][y];
if(x != 0)
tmp -= pref[i][j][x - 1];
cur[i][j] = tmp;
}
}
int ans = 0;
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
if(i == j) {
cur[i][j] = 0;
}
int tmp = min(cur[i][j], cur[j][i]);
ans += tmp;
cur[i][j] -= tmp;
cur[j][i] -= tmp;
}
}
int sisa = 0;
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
sisa += cur[i][j];
}
}
return ans + 2 * sisa / 3;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
9276 KB |
Output is correct |
2 |
Correct |
63 ms |
9336 KB |
Output is correct |
3 |
Correct |
98 ms |
8812 KB |
Output is correct |
4 |
Correct |
59 ms |
9328 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
6868 KB |
Output is correct |
5 |
Correct |
7 ms |
6852 KB |
Output is correct |
6 |
Correct |
7 ms |
6944 KB |
Output is correct |
7 |
Correct |
8 ms |
6500 KB |
Output is correct |
8 |
Correct |
8 ms |
6896 KB |
Output is correct |
9 |
Correct |
6 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
6868 KB |
Output is correct |
5 |
Correct |
7 ms |
6852 KB |
Output is correct |
6 |
Correct |
7 ms |
6944 KB |
Output is correct |
7 |
Correct |
8 ms |
6500 KB |
Output is correct |
8 |
Correct |
8 ms |
6896 KB |
Output is correct |
9 |
Correct |
6 ms |
6868 KB |
Output is correct |
10 |
Correct |
76 ms |
9308 KB |
Output is correct |
11 |
Correct |
68 ms |
9408 KB |
Output is correct |
12 |
Correct |
74 ms |
9244 KB |
Output is correct |
13 |
Correct |
63 ms |
9480 KB |
Output is correct |
14 |
Correct |
77 ms |
9712 KB |
Output is correct |
15 |
Correct |
72 ms |
9600 KB |
Output is correct |
16 |
Correct |
54 ms |
9184 KB |
Output is correct |
17 |
Correct |
57 ms |
9364 KB |
Output is correct |
18 |
Correct |
67 ms |
9636 KB |
Output is correct |
19 |
Correct |
52 ms |
9192 KB |
Output is correct |
20 |
Correct |
51 ms |
9368 KB |
Output is correct |
21 |
Correct |
51 ms |
9628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
6868 KB |
Output is correct |
5 |
Correct |
7 ms |
6852 KB |
Output is correct |
6 |
Correct |
7 ms |
6944 KB |
Output is correct |
7 |
Correct |
8 ms |
6500 KB |
Output is correct |
8 |
Correct |
8 ms |
6896 KB |
Output is correct |
9 |
Correct |
6 ms |
6868 KB |
Output is correct |
10 |
Correct |
8 ms |
6420 KB |
Output is correct |
11 |
Correct |
8 ms |
6868 KB |
Output is correct |
12 |
Correct |
7 ms |
6564 KB |
Output is correct |
13 |
Correct |
8 ms |
6868 KB |
Output is correct |
14 |
Correct |
10 ms |
6848 KB |
Output is correct |
15 |
Correct |
8 ms |
6848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
9276 KB |
Output is correct |
2 |
Correct |
63 ms |
9336 KB |
Output is correct |
3 |
Correct |
98 ms |
8812 KB |
Output is correct |
4 |
Correct |
59 ms |
9328 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
6868 KB |
Output is correct |
12 |
Correct |
7 ms |
6852 KB |
Output is correct |
13 |
Correct |
7 ms |
6944 KB |
Output is correct |
14 |
Correct |
8 ms |
6500 KB |
Output is correct |
15 |
Correct |
8 ms |
6896 KB |
Output is correct |
16 |
Correct |
6 ms |
6868 KB |
Output is correct |
17 |
Correct |
76 ms |
9308 KB |
Output is correct |
18 |
Correct |
68 ms |
9408 KB |
Output is correct |
19 |
Correct |
74 ms |
9244 KB |
Output is correct |
20 |
Correct |
63 ms |
9480 KB |
Output is correct |
21 |
Correct |
77 ms |
9712 KB |
Output is correct |
22 |
Correct |
72 ms |
9600 KB |
Output is correct |
23 |
Correct |
54 ms |
9184 KB |
Output is correct |
24 |
Correct |
57 ms |
9364 KB |
Output is correct |
25 |
Correct |
67 ms |
9636 KB |
Output is correct |
26 |
Correct |
52 ms |
9192 KB |
Output is correct |
27 |
Correct |
51 ms |
9368 KB |
Output is correct |
28 |
Correct |
51 ms |
9628 KB |
Output is correct |
29 |
Correct |
8 ms |
6420 KB |
Output is correct |
30 |
Correct |
8 ms |
6868 KB |
Output is correct |
31 |
Correct |
7 ms |
6564 KB |
Output is correct |
32 |
Correct |
8 ms |
6868 KB |
Output is correct |
33 |
Correct |
10 ms |
6848 KB |
Output is correct |
34 |
Correct |
8 ms |
6848 KB |
Output is correct |
35 |
Correct |
1 ms |
292 KB |
Output is correct |
36 |
Correct |
79 ms |
8820 KB |
Output is correct |
37 |
Correct |
66 ms |
9356 KB |
Output is correct |
38 |
Correct |
69 ms |
9352 KB |
Output is correct |
39 |
Correct |
75 ms |
9664 KB |
Output is correct |
40 |
Correct |
82 ms |
9720 KB |
Output is correct |
41 |
Correct |
9 ms |
6844 KB |
Output is correct |
42 |
Correct |
60 ms |
9312 KB |
Output is correct |
43 |
Correct |
67 ms |
9632 KB |
Output is correct |
44 |
Correct |
70 ms |
9608 KB |
Output is correct |
45 |
Correct |
55 ms |
9280 KB |
Output is correct |
46 |
Correct |
55 ms |
9620 KB |
Output is correct |
47 |
Correct |
63 ms |
9732 KB |
Output is correct |