#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int cnta[100010],cntc[100010],cntt[100010],cnta2[100010],cntc2[100010],cntt2[100010];
int cntat[100010],cntta[100010],cnttc[100010],cntct[100010],cntac[100010],cntca[100010];
void init(string a, string b) {
int n,i;
n=a.size();
for(i=0;i<n;i++){
if(a[i]=='A') cnta[i+1]++;
else if(a[i]=='C') cntc[i+1]++;
else cntt[i+1]++;
if(b[i]=='A') cnta2[i+1]++;
else if(b[i]=='C') cntc2[i+1]++;
else cntt2[i+1]++;
cnta[i+1]+=cnta[i];
cntc[i+1]+=cntc[i];
cntt[i+1]+=cntt[i];
cnta2[i+1]+=cnta2[i];
cntc2[i+1]+=cntc2[i];
cntt2[i+1]+=cntt2[i];
}
for(i=0;i<n;i++){
if(a[i]=='A'&&b[i]=='C') cntac[i+1]++;
else if(a[i]=='A'&&b[i]=='T') cntat[i+1]++;
else if(a[i]=='C'&&b[i]=='A') cntca[i+1]++;
else if(a[i]=='C'&&b[i]=='T') cntct[i+1]++;
else if(a[i]=='T'&&b[i]=='A') cntta[i+1]++;
else if(a[i]=='T'&&b[i]=='C') cnttc[i+1]++;
cntac[i+1]+=cntac[i];
cntct[i+1]+=cntct[i];
cntta[i+1]+=cntta[i];
cntat[i+1]+=cntat[i];
cntca[i+1]+=cntca[i];
cnttc[i+1]+=cnttc[i];
}
}
int get_distance(int x, int y) {
x++,y++;
int l,r;
if(cnta[y]-cnta[x-1]!=cnta2[y]-cnta2[x-1]) return -1;
if(cntc[y]-cntc[x-1]!=cntc2[y]-cntc2[x-1]) return -1;
if(cntt[y]-cntt[x-1]!=cntt2[y]-cntt2[x-1]) return -1;
return min(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1])+
min(cntac[y]-cntac[x-1],cntca[y]-cntca[x-1])+
min(cntct[y]-cntct[x-1],cnttc[y]-cnttc[x-1])+
2*(max(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1])-
min(cntat[y]-cntat[x-1],cntta[y]-cntta[x-1]));
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
Compilation message
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:41:9: warning: unused variable 'l' [-Wunused-variable]
41 | int l,r;
| ^
dna.cpp:41:11: warning: unused variable 'r' [-Wunused-variable]
41 | int l,r;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
7296 KB |
Output is correct |
2 |
Correct |
45 ms |
7672 KB |
Output is correct |
3 |
Correct |
45 ms |
7316 KB |
Output is correct |
4 |
Correct |
51 ms |
7680 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
5624 KB |
Output is correct |
5 |
Correct |
7 ms |
5708 KB |
Output is correct |
6 |
Correct |
7 ms |
5708 KB |
Output is correct |
7 |
Correct |
8 ms |
5356 KB |
Output is correct |
8 |
Correct |
8 ms |
5752 KB |
Output is correct |
9 |
Correct |
6 ms |
5824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
5624 KB |
Output is correct |
5 |
Correct |
7 ms |
5708 KB |
Output is correct |
6 |
Correct |
7 ms |
5708 KB |
Output is correct |
7 |
Correct |
8 ms |
5356 KB |
Output is correct |
8 |
Correct |
8 ms |
5752 KB |
Output is correct |
9 |
Correct |
6 ms |
5824 KB |
Output is correct |
10 |
Correct |
45 ms |
7300 KB |
Output is correct |
11 |
Correct |
47 ms |
7176 KB |
Output is correct |
12 |
Correct |
45 ms |
7272 KB |
Output is correct |
13 |
Correct |
43 ms |
7820 KB |
Output is correct |
14 |
Correct |
45 ms |
8048 KB |
Output is correct |
15 |
Correct |
42 ms |
8060 KB |
Output is correct |
16 |
Correct |
43 ms |
7696 KB |
Output is correct |
17 |
Correct |
43 ms |
7820 KB |
Output is correct |
18 |
Correct |
44 ms |
8052 KB |
Output is correct |
19 |
Correct |
40 ms |
7780 KB |
Output is correct |
20 |
Correct |
39 ms |
7948 KB |
Output is correct |
21 |
Correct |
41 ms |
8072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
5624 KB |
Output is correct |
5 |
Correct |
7 ms |
5708 KB |
Output is correct |
6 |
Correct |
7 ms |
5708 KB |
Output is correct |
7 |
Correct |
8 ms |
5356 KB |
Output is correct |
8 |
Correct |
8 ms |
5752 KB |
Output is correct |
9 |
Correct |
6 ms |
5824 KB |
Output is correct |
10 |
Correct |
7 ms |
5324 KB |
Output is correct |
11 |
Correct |
8 ms |
5708 KB |
Output is correct |
12 |
Correct |
10 ms |
5452 KB |
Output is correct |
13 |
Correct |
9 ms |
5708 KB |
Output is correct |
14 |
Correct |
9 ms |
5768 KB |
Output is correct |
15 |
Correct |
7 ms |
5708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
7296 KB |
Output is correct |
2 |
Correct |
45 ms |
7672 KB |
Output is correct |
3 |
Correct |
45 ms |
7316 KB |
Output is correct |
4 |
Correct |
51 ms |
7680 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
8 ms |
5624 KB |
Output is correct |
12 |
Correct |
7 ms |
5708 KB |
Output is correct |
13 |
Correct |
7 ms |
5708 KB |
Output is correct |
14 |
Correct |
8 ms |
5356 KB |
Output is correct |
15 |
Correct |
8 ms |
5752 KB |
Output is correct |
16 |
Correct |
6 ms |
5824 KB |
Output is correct |
17 |
Correct |
45 ms |
7300 KB |
Output is correct |
18 |
Correct |
47 ms |
7176 KB |
Output is correct |
19 |
Correct |
45 ms |
7272 KB |
Output is correct |
20 |
Correct |
43 ms |
7820 KB |
Output is correct |
21 |
Correct |
45 ms |
8048 KB |
Output is correct |
22 |
Correct |
42 ms |
8060 KB |
Output is correct |
23 |
Correct |
43 ms |
7696 KB |
Output is correct |
24 |
Correct |
43 ms |
7820 KB |
Output is correct |
25 |
Correct |
44 ms |
8052 KB |
Output is correct |
26 |
Correct |
40 ms |
7780 KB |
Output is correct |
27 |
Correct |
39 ms |
7948 KB |
Output is correct |
28 |
Correct |
41 ms |
8072 KB |
Output is correct |
29 |
Correct |
7 ms |
5324 KB |
Output is correct |
30 |
Correct |
8 ms |
5708 KB |
Output is correct |
31 |
Correct |
10 ms |
5452 KB |
Output is correct |
32 |
Correct |
9 ms |
5708 KB |
Output is correct |
33 |
Correct |
9 ms |
5768 KB |
Output is correct |
34 |
Correct |
7 ms |
5708 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
46 ms |
7252 KB |
Output is correct |
37 |
Correct |
46 ms |
7692 KB |
Output is correct |
38 |
Correct |
46 ms |
7808 KB |
Output is correct |
39 |
Correct |
48 ms |
8108 KB |
Output is correct |
40 |
Correct |
47 ms |
8064 KB |
Output is correct |
41 |
Correct |
6 ms |
5708 KB |
Output is correct |
42 |
Correct |
43 ms |
7820 KB |
Output is correct |
43 |
Correct |
44 ms |
8064 KB |
Output is correct |
44 |
Correct |
44 ms |
8148 KB |
Output is correct |
45 |
Correct |
40 ms |
7788 KB |
Output is correct |
46 |
Correct |
41 ms |
8140 KB |
Output is correct |
47 |
Correct |
42 ms |
8064 KB |
Output is correct |