#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
int a[100005][6], cnta[100005][3], cntb[100005][3] /* AC, AT, CA, CT, TA, TC */;
void init(string A, string B)
{
for(int i=0; i<(int)A.length(); i++)
{
if(A[i]=='A' and B[i]=='C') a[i+1][0]=1;
if(A[i]=='A' and B[i]=='T') a[i+1][1]=1;
if(A[i]=='C' and B[i]=='A') a[i+1][2]=1;
if(A[i]=='C' and B[i]=='T') a[i+1][3]=1;
if(A[i]=='T' and B[i]=='A') a[i+1][4]=1;
if(A[i]=='T' and B[i]=='C') a[i+1][5]=1;
for(int j=0; j<6; j++)
a[i+1][j]+=a[i][j];
if(A[i]=='A') cnta[i+1][0]=1;
if(A[i]=='C') cnta[i+1][1]=1;
if(A[i]=='T') cnta[i+1][2]=1;
if(B[i]=='A') cntb[i+1][0]=1;
if(B[i]=='C') cntb[i+1][1]=1;
if(B[i]=='T') cntb[i+1][2]=1;
cnta[i+1][0]+=cnta[i][0];
cnta[i+1][1]+=cnta[i][1];
cnta[i+1][2]+=cnta[i][2];
cntb[i+1][0]+=cntb[i][0];
cntb[i+1][1]+=cntb[i][1];
cntb[i+1][2]+=cntb[i][2];
}
}
int get_distance(int x, int y)
{
if(cnta[y+1][0]-cnta[x][0]!=cntb[y+1][0]-cntb[x][0] or
cnta[y+1][1]-cnta[x][1]!=cntb[y+1][1]-cntb[x][1] or
cnta[y+1][2]-cnta[x][2]!=cntb[y+1][2]-cntb[x][2]) return -1;
int num=0, ans=0, k;
k=min(a[y+1][0]-a[x][0], a[y+1][2]-a[x][2]);
num+=k;
ans+=a[y+1][0]-a[x][0]-k;
ans+=a[y+1][2]-a[x][2]-k;
k=min(a[y+1][1]-a[x][1], a[y+1][4]-a[x][4]);
num+=k;
ans+=a[y+1][1]-a[x][1]-k;
ans+=a[y+1][4]-a[x][4]-k;
k=min(a[y+1][3]-a[x][3], a[y+1][5]-a[x][5]);
num+=k;
ans+=a[y+1][3]-a[x][3]-k;
ans+=a[y+1][5]-a[x][5]-k;
return num+ans/3*2;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
8052 KB |
Output is correct |
2 |
Correct |
28 ms |
8224 KB |
Output is correct |
3 |
Correct |
27 ms |
7756 KB |
Output is correct |
4 |
Correct |
28 ms |
8120 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
5 ms |
5700 KB |
Output is correct |
6 |
Correct |
5 ms |
5676 KB |
Output is correct |
7 |
Correct |
6 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
5 ms |
5700 KB |
Output is correct |
6 |
Correct |
5 ms |
5676 KB |
Output is correct |
7 |
Correct |
6 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5696 KB |
Output is correct |
10 |
Correct |
30 ms |
8136 KB |
Output is correct |
11 |
Correct |
29 ms |
8176 KB |
Output is correct |
12 |
Correct |
29 ms |
8136 KB |
Output is correct |
13 |
Correct |
32 ms |
8296 KB |
Output is correct |
14 |
Correct |
29 ms |
8560 KB |
Output is correct |
15 |
Correct |
34 ms |
8436 KB |
Output is correct |
16 |
Correct |
35 ms |
8040 KB |
Output is correct |
17 |
Correct |
29 ms |
8212 KB |
Output is correct |
18 |
Correct |
29 ms |
8460 KB |
Output is correct |
19 |
Correct |
27 ms |
8080 KB |
Output is correct |
20 |
Correct |
35 ms |
8292 KB |
Output is correct |
21 |
Correct |
29 ms |
8416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
5 ms |
5700 KB |
Output is correct |
6 |
Correct |
5 ms |
5676 KB |
Output is correct |
7 |
Correct |
6 ms |
5332 KB |
Output is correct |
8 |
Correct |
6 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5696 KB |
Output is correct |
10 |
Correct |
7 ms |
5204 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5692 KB |
Output is correct |
14 |
Correct |
5 ms |
5716 KB |
Output is correct |
15 |
Correct |
4 ms |
5684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
8052 KB |
Output is correct |
2 |
Correct |
28 ms |
8224 KB |
Output is correct |
3 |
Correct |
27 ms |
7756 KB |
Output is correct |
4 |
Correct |
28 ms |
8120 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
5 ms |
5700 KB |
Output is correct |
13 |
Correct |
5 ms |
5676 KB |
Output is correct |
14 |
Correct |
6 ms |
5332 KB |
Output is correct |
15 |
Correct |
6 ms |
5716 KB |
Output is correct |
16 |
Correct |
4 ms |
5696 KB |
Output is correct |
17 |
Correct |
30 ms |
8136 KB |
Output is correct |
18 |
Correct |
29 ms |
8176 KB |
Output is correct |
19 |
Correct |
29 ms |
8136 KB |
Output is correct |
20 |
Correct |
32 ms |
8296 KB |
Output is correct |
21 |
Correct |
29 ms |
8560 KB |
Output is correct |
22 |
Correct |
34 ms |
8436 KB |
Output is correct |
23 |
Correct |
35 ms |
8040 KB |
Output is correct |
24 |
Correct |
29 ms |
8212 KB |
Output is correct |
25 |
Correct |
29 ms |
8460 KB |
Output is correct |
26 |
Correct |
27 ms |
8080 KB |
Output is correct |
27 |
Correct |
35 ms |
8292 KB |
Output is correct |
28 |
Correct |
29 ms |
8416 KB |
Output is correct |
29 |
Correct |
7 ms |
5204 KB |
Output is correct |
30 |
Correct |
5 ms |
5716 KB |
Output is correct |
31 |
Correct |
6 ms |
5332 KB |
Output is correct |
32 |
Correct |
6 ms |
5692 KB |
Output is correct |
33 |
Correct |
5 ms |
5716 KB |
Output is correct |
34 |
Correct |
4 ms |
5684 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
31 ms |
7640 KB |
Output is correct |
37 |
Correct |
31 ms |
8232 KB |
Output is correct |
38 |
Correct |
31 ms |
8216 KB |
Output is correct |
39 |
Correct |
30 ms |
8512 KB |
Output is correct |
40 |
Correct |
31 ms |
8564 KB |
Output is correct |
41 |
Correct |
4 ms |
5716 KB |
Output is correct |
42 |
Correct |
29 ms |
8156 KB |
Output is correct |
43 |
Correct |
30 ms |
8436 KB |
Output is correct |
44 |
Correct |
31 ms |
8496 KB |
Output is correct |
45 |
Correct |
29 ms |
8100 KB |
Output is correct |
46 |
Correct |
27 ms |
8432 KB |
Output is correct |
47 |
Correct |
33 ms |
8436 KB |
Output is correct |