#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
vector<int> match, ac, ca, at, ta, ct, tc, A, C, T;
void init(std::string a, std::string b) {
int n = a.size();
match.resize(n,0);
ac.resize(n,0);
ca.resize(n,0);
at.resize(n,0);
ta.resize(n,0);
ct.resize(n,0);
tc.resize(n,0);
A.resize(n,0);
C.resize(n,0);
T.resize(n,0);
for(int i = 0; i < n; ++i){
if(a[i] == b[i])match[i]=1;
if(a[i] == 'A' && b[i] == 'C')ac[i]=1;
if(a[i] == 'C' && b[i] == 'A')ca[i]=1;
if(a[i] == 'A' && b[i] == 'T')at[i]=1;
if(a[i] == 'T' && b[i] == 'A')ta[i]=1;
if(a[i] == 'C' && b[i] == 'T')ct[i]=1;
if(a[i] == 'T' && b[i] == 'C')tc[i]=1;
if(a[i] == 'A')A[i]++;
if(a[i] == 'C')C[i]++;
if(a[i] == 'T')T[i]++;
if(b[i] == 'A')A[i]--;
if(b[i] == 'C')C[i]--;
if(b[i] == 'T')T[i]--;
}
for(int i = 1; i < n; ++i){
match[i]+=match[i-1];
ac[i]+=ac[i-1];
ca[i]+=ca[i-1];
at[i]+=at[i-1];
ta[i]+=ta[i-1];
ct[i]+=ct[i-1];
tc[i]+=tc[i-1];
A[i]+=A[i-1];
C[i]+=C[i-1];
T[i]+=T[i-1];
}
}
int get_distance(int x, int y) {
int ans = 0;
int dis = y-x+1;
if(x == 0){
if(A[y]|C[y]|T[y])return -1;
dis-=match[y];
ans+=min(ac[y],ca[y]);
ans+=min(at[y],ta[y]);
ans+=min(tc[y],ct[y]);
dis-=2*ans;
return ans+(dis/3)*2;
}
else{
if((A[y]-A[x-1])|(C[y]-C[x-1])|(T[y]-T[x-1]))return -1;
dis-=match[y]-match[x-1];
ans+=min(ac[y]-ac[x-1],ca[y]-ca[x-1]);
ans+=min(at[y]-at[x-1],ta[y]-ta[x-1]);
ans+=min(tc[y]-tc[x-1],ct[y]-ct[x-1]);
dis-=2*ans;
return ans+(dis/3)*2;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
6020 KB |
Output is correct |
2 |
Correct |
51 ms |
6008 KB |
Output is correct |
3 |
Correct |
49 ms |
5728 KB |
Output is correct |
4 |
Correct |
64 ms |
6008 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 |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
276 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
15 ms |
4684 KB |
Output is correct |
5 |
Correct |
15 ms |
4816 KB |
Output is correct |
6 |
Correct |
16 ms |
4768 KB |
Output is correct |
7 |
Correct |
14 ms |
4448 KB |
Output is correct |
8 |
Correct |
14 ms |
4812 KB |
Output is correct |
9 |
Correct |
13 ms |
4812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
276 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
15 ms |
4684 KB |
Output is correct |
5 |
Correct |
15 ms |
4816 KB |
Output is correct |
6 |
Correct |
16 ms |
4768 KB |
Output is correct |
7 |
Correct |
14 ms |
4448 KB |
Output is correct |
8 |
Correct |
14 ms |
4812 KB |
Output is correct |
9 |
Correct |
13 ms |
4812 KB |
Output is correct |
10 |
Correct |
49 ms |
6020 KB |
Output is correct |
11 |
Correct |
51 ms |
6040 KB |
Output is correct |
12 |
Correct |
50 ms |
6104 KB |
Output is correct |
13 |
Correct |
62 ms |
6252 KB |
Output is correct |
14 |
Correct |
51 ms |
6396 KB |
Output is correct |
15 |
Correct |
50 ms |
6288 KB |
Output is correct |
16 |
Correct |
49 ms |
6100 KB |
Output is correct |
17 |
Correct |
51 ms |
6284 KB |
Output is correct |
18 |
Correct |
49 ms |
6392 KB |
Output is correct |
19 |
Correct |
48 ms |
6160 KB |
Output is correct |
20 |
Correct |
46 ms |
6284 KB |
Output is correct |
21 |
Correct |
48 ms |
6384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
276 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
15 ms |
4684 KB |
Output is correct |
5 |
Correct |
15 ms |
4816 KB |
Output is correct |
6 |
Correct |
16 ms |
4768 KB |
Output is correct |
7 |
Correct |
14 ms |
4448 KB |
Output is correct |
8 |
Correct |
14 ms |
4812 KB |
Output is correct |
9 |
Correct |
13 ms |
4812 KB |
Output is correct |
10 |
Correct |
13 ms |
4440 KB |
Output is correct |
11 |
Correct |
16 ms |
4812 KB |
Output is correct |
12 |
Correct |
14 ms |
4536 KB |
Output is correct |
13 |
Correct |
15 ms |
4812 KB |
Output is correct |
14 |
Correct |
15 ms |
4820 KB |
Output is correct |
15 |
Correct |
14 ms |
4812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
6020 KB |
Output is correct |
2 |
Correct |
51 ms |
6008 KB |
Output is correct |
3 |
Correct |
49 ms |
5728 KB |
Output is correct |
4 |
Correct |
64 ms |
6008 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 |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
276 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
15 ms |
4684 KB |
Output is correct |
12 |
Correct |
15 ms |
4816 KB |
Output is correct |
13 |
Correct |
16 ms |
4768 KB |
Output is correct |
14 |
Correct |
14 ms |
4448 KB |
Output is correct |
15 |
Correct |
14 ms |
4812 KB |
Output is correct |
16 |
Correct |
13 ms |
4812 KB |
Output is correct |
17 |
Correct |
49 ms |
6020 KB |
Output is correct |
18 |
Correct |
51 ms |
6040 KB |
Output is correct |
19 |
Correct |
50 ms |
6104 KB |
Output is correct |
20 |
Correct |
62 ms |
6252 KB |
Output is correct |
21 |
Correct |
51 ms |
6396 KB |
Output is correct |
22 |
Correct |
50 ms |
6288 KB |
Output is correct |
23 |
Correct |
49 ms |
6100 KB |
Output is correct |
24 |
Correct |
51 ms |
6284 KB |
Output is correct |
25 |
Correct |
49 ms |
6392 KB |
Output is correct |
26 |
Correct |
48 ms |
6160 KB |
Output is correct |
27 |
Correct |
46 ms |
6284 KB |
Output is correct |
28 |
Correct |
48 ms |
6384 KB |
Output is correct |
29 |
Correct |
13 ms |
4440 KB |
Output is correct |
30 |
Correct |
16 ms |
4812 KB |
Output is correct |
31 |
Correct |
14 ms |
4536 KB |
Output is correct |
32 |
Correct |
15 ms |
4812 KB |
Output is correct |
33 |
Correct |
15 ms |
4820 KB |
Output is correct |
34 |
Correct |
14 ms |
4812 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
49 ms |
5736 KB |
Output is correct |
37 |
Correct |
64 ms |
6016 KB |
Output is correct |
38 |
Correct |
51 ms |
6132 KB |
Output is correct |
39 |
Correct |
61 ms |
6400 KB |
Output is correct |
40 |
Correct |
52 ms |
6420 KB |
Output is correct |
41 |
Correct |
15 ms |
4772 KB |
Output is correct |
42 |
Correct |
61 ms |
6144 KB |
Output is correct |
43 |
Correct |
50 ms |
6400 KB |
Output is correct |
44 |
Correct |
52 ms |
6384 KB |
Output is correct |
45 |
Correct |
47 ms |
6124 KB |
Output is correct |
46 |
Correct |
47 ms |
6392 KB |
Output is correct |
47 |
Correct |
47 ms |
6392 KB |
Output is correct |