#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int, 9> > pre;
template<typename T, size_t s>
array<T, s> operator-(array<T, s> a, array<T, s> const&b){
for(size_t i = 0; i < s; ++i){
a[i] -= b[i];
}
return a;
}
int deco(char const c){
switch(c){
case 'A':
return 0;
case 'T':
return 1;
case 'C':
return 2;
default:
assert(0);
return -1;
}
}
void init(string a, string b) {
n = a.size();
pre.assign(n+1, array<int, 9>{});
for(int i=0; i<n; ++i){
pre[i+1] = pre[i];
++pre[i+1][deco(a[i])*3+deco(b[i])];
}
}
int get_distance(int x, int y) {
auto tmp = pre[y+1] - pre[x];
int ret = 0;
for(int i:{0,1,2}){
const int j = (i+1)%3;
const int x = min(tmp[3*i+j], tmp[3*j+i]);
ret += x;
tmp[3*i+j] -= x;
tmp[3*j+i] -= x;
}
if(tmp[3*0+1] != tmp[3*1+2] || tmp[3*0+1] != tmp[3*2+0]){
return -1;
}
if(tmp[3*1+0] != tmp[3*2+1] || tmp[3*1+0] != tmp[3*0+2]){
return -1;
}
ret += 2*tmp[3*0+1];
ret += 2*tmp[3*0+2];
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5760 KB |
Output is correct |
2 |
Correct |
44 ms |
5876 KB |
Output is correct |
3 |
Correct |
42 ms |
5528 KB |
Output is correct |
4 |
Correct |
44 ms |
5760 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4428 KB |
Output is correct |
5 |
Correct |
7 ms |
4556 KB |
Output is correct |
6 |
Correct |
6 ms |
4428 KB |
Output is correct |
7 |
Correct |
5 ms |
4172 KB |
Output is correct |
8 |
Correct |
5 ms |
4568 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4428 KB |
Output is correct |
5 |
Correct |
7 ms |
4556 KB |
Output is correct |
6 |
Correct |
6 ms |
4428 KB |
Output is correct |
7 |
Correct |
5 ms |
4172 KB |
Output is correct |
8 |
Correct |
5 ms |
4568 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
10 |
Correct |
44 ms |
5748 KB |
Output is correct |
11 |
Correct |
46 ms |
5788 KB |
Output is correct |
12 |
Correct |
42 ms |
5900 KB |
Output is correct |
13 |
Correct |
50 ms |
6044 KB |
Output is correct |
14 |
Correct |
43 ms |
6212 KB |
Output is correct |
15 |
Correct |
45 ms |
6060 KB |
Output is correct |
16 |
Correct |
45 ms |
5912 KB |
Output is correct |
17 |
Correct |
43 ms |
6028 KB |
Output is correct |
18 |
Correct |
45 ms |
6276 KB |
Output is correct |
19 |
Correct |
39 ms |
5900 KB |
Output is correct |
20 |
Correct |
40 ms |
6052 KB |
Output is correct |
21 |
Correct |
40 ms |
6188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4428 KB |
Output is correct |
5 |
Correct |
7 ms |
4556 KB |
Output is correct |
6 |
Correct |
6 ms |
4428 KB |
Output is correct |
7 |
Correct |
5 ms |
4172 KB |
Output is correct |
8 |
Correct |
5 ms |
4568 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
10 |
Correct |
6 ms |
4172 KB |
Output is correct |
11 |
Correct |
6 ms |
4556 KB |
Output is correct |
12 |
Correct |
5 ms |
4172 KB |
Output is correct |
13 |
Correct |
6 ms |
4428 KB |
Output is correct |
14 |
Correct |
6 ms |
4556 KB |
Output is correct |
15 |
Correct |
5 ms |
4464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5760 KB |
Output is correct |
2 |
Correct |
44 ms |
5876 KB |
Output is correct |
3 |
Correct |
42 ms |
5528 KB |
Output is correct |
4 |
Correct |
44 ms |
5760 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
6 ms |
4428 KB |
Output is correct |
12 |
Correct |
7 ms |
4556 KB |
Output is correct |
13 |
Correct |
6 ms |
4428 KB |
Output is correct |
14 |
Correct |
5 ms |
4172 KB |
Output is correct |
15 |
Correct |
5 ms |
4568 KB |
Output is correct |
16 |
Correct |
5 ms |
4556 KB |
Output is correct |
17 |
Correct |
44 ms |
5748 KB |
Output is correct |
18 |
Correct |
46 ms |
5788 KB |
Output is correct |
19 |
Correct |
42 ms |
5900 KB |
Output is correct |
20 |
Correct |
50 ms |
6044 KB |
Output is correct |
21 |
Correct |
43 ms |
6212 KB |
Output is correct |
22 |
Correct |
45 ms |
6060 KB |
Output is correct |
23 |
Correct |
45 ms |
5912 KB |
Output is correct |
24 |
Correct |
43 ms |
6028 KB |
Output is correct |
25 |
Correct |
45 ms |
6276 KB |
Output is correct |
26 |
Correct |
39 ms |
5900 KB |
Output is correct |
27 |
Correct |
40 ms |
6052 KB |
Output is correct |
28 |
Correct |
40 ms |
6188 KB |
Output is correct |
29 |
Correct |
6 ms |
4172 KB |
Output is correct |
30 |
Correct |
6 ms |
4556 KB |
Output is correct |
31 |
Correct |
5 ms |
4172 KB |
Output is correct |
32 |
Correct |
6 ms |
4428 KB |
Output is correct |
33 |
Correct |
6 ms |
4556 KB |
Output is correct |
34 |
Correct |
5 ms |
4464 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
43 ms |
5528 KB |
Output is correct |
37 |
Correct |
43 ms |
5812 KB |
Output is correct |
38 |
Correct |
46 ms |
5928 KB |
Output is correct |
39 |
Correct |
43 ms |
6144 KB |
Output is correct |
40 |
Correct |
43 ms |
6208 KB |
Output is correct |
41 |
Correct |
5 ms |
4556 KB |
Output is correct |
42 |
Correct |
41 ms |
5920 KB |
Output is correct |
43 |
Correct |
65 ms |
6196 KB |
Output is correct |
44 |
Correct |
49 ms |
6192 KB |
Output is correct |
45 |
Correct |
42 ms |
6028 KB |
Output is correct |
46 |
Correct |
40 ms |
6272 KB |
Output is correct |
47 |
Correct |
40 ms |
6312 KB |
Output is correct |