#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=(5e5)+10;
int s[maxn][6],n;
int cnt[maxn][3];
int id[300][300],dy[300];
void init(string a,string b) {
n=a.size();
dy['A']=0,dy['C']=1,dy['T']=2;
id['C']['A']=0,id['A']['T']=2,id['A']['C']=4;
id['T']['A']=1,id['C']['T']=3,id['T']['C']=5;
for (int i=1;i<=n;i++) {
for (int j=0;j<6;j++) s[i][j]=s[i-1][j];
if (a[i-1]!=b[i-1]) {
s[i][id[a[i-1]][b[i-1]]]++;
}
for (int j=0;j<3;j++) cnt[i][j]=cnt[i-1][j];
cnt[i][dy[a[i-1]]]++;
cnt[i][dy[b[i-1]]]--;
}
}
int get_distance(int x, int y) {
int d[10];
for (int i=0;i<3;i++) if (cnt[y+1][i]!=cnt[x][i]) return -1;
for (int i=0;i<6;i++) d[i]=s[y+1][i]-s[x][i];
int ans=0,t=min(d[0],d[4]);
d[0]-=t,d[4]-=t,ans+=t;
t=min(d[2],d[1]),d[1]-=t,d[2]-=t,ans+=t;
t=min(d[3],d[5]),d[3]-=t,d[5]-=t,ans+=t;
// printf("%d %d %d\n",d[0]+d[4],d[1]+d[2],d[3]+d[5]);
return ans+(d[3]+d[5])*2;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:16:18: warning: array subscript has type 'char' [-Wchar-subscripts]
16 | s[i][id[a[i-1]][b[i-1]]]++;
| ^
dna.cpp:16:26: warning: array subscript has type 'char' [-Wchar-subscripts]
16 | s[i][id[a[i-1]][b[i-1]]]++;
| ^
dna.cpp:19:19: warning: array subscript has type 'char' [-Wchar-subscripts]
19 | cnt[i][dy[a[i-1]]]++;
| ^
dna.cpp:20:19: warning: array subscript has type 'char' [-Wchar-subscripts]
20 | cnt[i][dy[b[i-1]]]--;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5616 KB |
Output is correct |
2 |
Correct |
46 ms |
5628 KB |
Output is correct |
3 |
Correct |
42 ms |
5340 KB |
Output is correct |
4 |
Correct |
41 ms |
5648 KB |
Output is correct |
5 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4324 KB |
Output is correct |
5 |
Correct |
7 ms |
4348 KB |
Output is correct |
6 |
Correct |
6 ms |
4364 KB |
Output is correct |
7 |
Correct |
6 ms |
4044 KB |
Output is correct |
8 |
Correct |
5 ms |
4428 KB |
Output is correct |
9 |
Correct |
5 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4324 KB |
Output is correct |
5 |
Correct |
7 ms |
4348 KB |
Output is correct |
6 |
Correct |
6 ms |
4364 KB |
Output is correct |
7 |
Correct |
6 ms |
4044 KB |
Output is correct |
8 |
Correct |
5 ms |
4428 KB |
Output is correct |
9 |
Correct |
5 ms |
4428 KB |
Output is correct |
10 |
Correct |
47 ms |
5628 KB |
Output is correct |
11 |
Correct |
40 ms |
5736 KB |
Output is correct |
12 |
Correct |
43 ms |
5728 KB |
Output is correct |
13 |
Correct |
44 ms |
5876 KB |
Output is correct |
14 |
Correct |
49 ms |
6012 KB |
Output is correct |
15 |
Correct |
41 ms |
6020 KB |
Output is correct |
16 |
Correct |
41 ms |
5776 KB |
Output is correct |
17 |
Correct |
46 ms |
5828 KB |
Output is correct |
18 |
Correct |
47 ms |
6012 KB |
Output is correct |
19 |
Correct |
43 ms |
5996 KB |
Output is correct |
20 |
Correct |
40 ms |
5880 KB |
Output is correct |
21 |
Correct |
39 ms |
6144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
6 ms |
4324 KB |
Output is correct |
5 |
Correct |
7 ms |
4348 KB |
Output is correct |
6 |
Correct |
6 ms |
4364 KB |
Output is correct |
7 |
Correct |
6 ms |
4044 KB |
Output is correct |
8 |
Correct |
5 ms |
4428 KB |
Output is correct |
9 |
Correct |
5 ms |
4428 KB |
Output is correct |
10 |
Correct |
5 ms |
4044 KB |
Output is correct |
11 |
Correct |
6 ms |
4428 KB |
Output is correct |
12 |
Correct |
5 ms |
4140 KB |
Output is correct |
13 |
Correct |
6 ms |
4352 KB |
Output is correct |
14 |
Correct |
6 ms |
4428 KB |
Output is correct |
15 |
Correct |
6 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5616 KB |
Output is correct |
2 |
Correct |
46 ms |
5628 KB |
Output is correct |
3 |
Correct |
42 ms |
5340 KB |
Output is correct |
4 |
Correct |
41 ms |
5648 KB |
Output is correct |
5 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
6 ms |
4324 KB |
Output is correct |
12 |
Correct |
7 ms |
4348 KB |
Output is correct |
13 |
Correct |
6 ms |
4364 KB |
Output is correct |
14 |
Correct |
6 ms |
4044 KB |
Output is correct |
15 |
Correct |
5 ms |
4428 KB |
Output is correct |
16 |
Correct |
5 ms |
4428 KB |
Output is correct |
17 |
Correct |
47 ms |
5628 KB |
Output is correct |
18 |
Correct |
40 ms |
5736 KB |
Output is correct |
19 |
Correct |
43 ms |
5728 KB |
Output is correct |
20 |
Correct |
44 ms |
5876 KB |
Output is correct |
21 |
Correct |
49 ms |
6012 KB |
Output is correct |
22 |
Correct |
41 ms |
6020 KB |
Output is correct |
23 |
Correct |
41 ms |
5776 KB |
Output is correct |
24 |
Correct |
46 ms |
5828 KB |
Output is correct |
25 |
Correct |
47 ms |
6012 KB |
Output is correct |
26 |
Correct |
43 ms |
5996 KB |
Output is correct |
27 |
Correct |
40 ms |
5880 KB |
Output is correct |
28 |
Correct |
39 ms |
6144 KB |
Output is correct |
29 |
Correct |
5 ms |
4044 KB |
Output is correct |
30 |
Correct |
6 ms |
4428 KB |
Output is correct |
31 |
Correct |
5 ms |
4140 KB |
Output is correct |
32 |
Correct |
6 ms |
4352 KB |
Output is correct |
33 |
Correct |
6 ms |
4428 KB |
Output is correct |
34 |
Correct |
6 ms |
4428 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
41 ms |
5352 KB |
Output is correct |
37 |
Correct |
54 ms |
5644 KB |
Output is correct |
38 |
Correct |
44 ms |
5772 KB |
Output is correct |
39 |
Correct |
47 ms |
6048 KB |
Output is correct |
40 |
Correct |
63 ms |
6020 KB |
Output is correct |
41 |
Correct |
5 ms |
4428 KB |
Output is correct |
42 |
Correct |
39 ms |
5752 KB |
Output is correct |
43 |
Correct |
45 ms |
6004 KB |
Output is correct |
44 |
Correct |
52 ms |
6060 KB |
Output is correct |
45 |
Correct |
38 ms |
5880 KB |
Output is correct |
46 |
Correct |
46 ms |
6020 KB |
Output is correct |
47 |
Correct |
50 ms |
6140 KB |
Output is correct |