#include "dna.h"
#include <cassert>
constexpr int maxn = 1e5+10;
int a[maxn], b[maxn], pref[maxn][6], qtd[maxn][2][3], n;
int tp(char c) { return c == 'A' ? 0 : c == 'T' ? 1 : 2; }
int df(int a, int b) {
if(a > b) return 5 - df(b, a);
if(a == 0 && b == 1) return 0;
if(a == 0 && b == 2) return 1;
return 2; // [1, 2]
}
void init(std::string s1, std::string s2) {
n = (int)s1.size();
for(int i = 0; i < n; i++)
a[i] = tp(s1[i]);
for(int i = 0; i < n; i++)
b[i] = tp(s2[i]);
for(int i = 0; i < n; i++) {
if(i) {
for(int j = 0; j < 6; j++)
pref[i][j] = pref[i-1][j];
for(int j = 0; j < 3; j++)
for(int k = 0; k < 2; k++)
qtd[i][k][j] = qtd[i-1][k][j];
}
qtd[i][0][a[i]]++;
qtd[i][1][b[i]]++;
if(a[i] == b[i]) continue; // não adiciono em canto nenhum
pref[i][df(a[i], b[i])]++;
}
}
bool valid(int x, int y) {
for(int k = 0; k < 3; k++)
if(qtd[y][0][k] - (x ? qtd[x-1][0][k] : 0) != qtd[y][1][k] - (x ? qtd[x-1][1][k] : 0))
return 0;
return 1;
}
int get_distance(int x, int y) {
if(!valid(x, y)) return -1;
int val[6]{};
for(int j = 0; j < 6; j++)
val[j] = pref[y][j];
if(x) for(int j = 0; j < 6; j++)
val[j] -= pref[x-1][j];
int ans = 0, sobra = 0;
for(int j = 0; j < 3; j++) {
int aq = std::min(val[j], val[5-j]);
ans += aq;
val[j] -= aq, val[5-j] -= aq;
sobra += val[j] + val[5-j];
}
ans += (sobra / 3) * 2;
assert(!(sobra%3));
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
8964 KB |
Output is correct |
2 |
Correct |
34 ms |
8920 KB |
Output is correct |
3 |
Correct |
33 ms |
8444 KB |
Output is correct |
4 |
Correct |
35 ms |
8876 KB |
Output is correct |
5 |
Correct |
1 ms |
276 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
6448 KB |
Output is correct |
5 |
Correct |
6 ms |
6476 KB |
Output is correct |
6 |
Correct |
6 ms |
6388 KB |
Output is correct |
7 |
Correct |
6 ms |
6060 KB |
Output is correct |
8 |
Correct |
6 ms |
6476 KB |
Output is correct |
9 |
Correct |
5 ms |
6468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
6448 KB |
Output is correct |
5 |
Correct |
6 ms |
6476 KB |
Output is correct |
6 |
Correct |
6 ms |
6388 KB |
Output is correct |
7 |
Correct |
6 ms |
6060 KB |
Output is correct |
8 |
Correct |
6 ms |
6476 KB |
Output is correct |
9 |
Correct |
5 ms |
6468 KB |
Output is correct |
10 |
Correct |
33 ms |
8900 KB |
Output is correct |
11 |
Correct |
32 ms |
8952 KB |
Output is correct |
12 |
Correct |
33 ms |
8788 KB |
Output is correct |
13 |
Correct |
36 ms |
8972 KB |
Output is correct |
14 |
Correct |
34 ms |
9304 KB |
Output is correct |
15 |
Correct |
33 ms |
9184 KB |
Output is correct |
16 |
Correct |
30 ms |
8788 KB |
Output is correct |
17 |
Correct |
32 ms |
8924 KB |
Output is correct |
18 |
Correct |
32 ms |
9220 KB |
Output is correct |
19 |
Correct |
29 ms |
8772 KB |
Output is correct |
20 |
Correct |
31 ms |
8956 KB |
Output is correct |
21 |
Correct |
36 ms |
9216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
6448 KB |
Output is correct |
5 |
Correct |
6 ms |
6476 KB |
Output is correct |
6 |
Correct |
6 ms |
6388 KB |
Output is correct |
7 |
Correct |
6 ms |
6060 KB |
Output is correct |
8 |
Correct |
6 ms |
6476 KB |
Output is correct |
9 |
Correct |
5 ms |
6468 KB |
Output is correct |
10 |
Correct |
6 ms |
5936 KB |
Output is correct |
11 |
Correct |
6 ms |
6476 KB |
Output is correct |
12 |
Correct |
6 ms |
6092 KB |
Output is correct |
13 |
Correct |
6 ms |
6444 KB |
Output is correct |
14 |
Correct |
6 ms |
6476 KB |
Output is correct |
15 |
Correct |
6 ms |
6424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
8964 KB |
Output is correct |
2 |
Correct |
34 ms |
8920 KB |
Output is correct |
3 |
Correct |
33 ms |
8444 KB |
Output is correct |
4 |
Correct |
35 ms |
8876 KB |
Output is correct |
5 |
Correct |
1 ms |
276 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
5 ms |
6448 KB |
Output is correct |
12 |
Correct |
6 ms |
6476 KB |
Output is correct |
13 |
Correct |
6 ms |
6388 KB |
Output is correct |
14 |
Correct |
6 ms |
6060 KB |
Output is correct |
15 |
Correct |
6 ms |
6476 KB |
Output is correct |
16 |
Correct |
5 ms |
6468 KB |
Output is correct |
17 |
Correct |
33 ms |
8900 KB |
Output is correct |
18 |
Correct |
32 ms |
8952 KB |
Output is correct |
19 |
Correct |
33 ms |
8788 KB |
Output is correct |
20 |
Correct |
36 ms |
8972 KB |
Output is correct |
21 |
Correct |
34 ms |
9304 KB |
Output is correct |
22 |
Correct |
33 ms |
9184 KB |
Output is correct |
23 |
Correct |
30 ms |
8788 KB |
Output is correct |
24 |
Correct |
32 ms |
8924 KB |
Output is correct |
25 |
Correct |
32 ms |
9220 KB |
Output is correct |
26 |
Correct |
29 ms |
8772 KB |
Output is correct |
27 |
Correct |
31 ms |
8956 KB |
Output is correct |
28 |
Correct |
36 ms |
9216 KB |
Output is correct |
29 |
Correct |
6 ms |
5936 KB |
Output is correct |
30 |
Correct |
6 ms |
6476 KB |
Output is correct |
31 |
Correct |
6 ms |
6092 KB |
Output is correct |
32 |
Correct |
6 ms |
6444 KB |
Output is correct |
33 |
Correct |
6 ms |
6476 KB |
Output is correct |
34 |
Correct |
6 ms |
6424 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
33 ms |
8392 KB |
Output is correct |
37 |
Correct |
37 ms |
8936 KB |
Output is correct |
38 |
Correct |
34 ms |
8908 KB |
Output is correct |
39 |
Correct |
33 ms |
9304 KB |
Output is correct |
40 |
Correct |
36 ms |
9320 KB |
Output is correct |
41 |
Correct |
5 ms |
6424 KB |
Output is correct |
42 |
Correct |
31 ms |
8928 KB |
Output is correct |
43 |
Correct |
34 ms |
9216 KB |
Output is correct |
44 |
Correct |
32 ms |
9216 KB |
Output is correct |
45 |
Correct |
31 ms |
8820 KB |
Output is correct |
46 |
Correct |
30 ms |
9188 KB |
Output is correct |
47 |
Correct |
30 ms |
9180 KB |
Output is correct |