#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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
6764 KB |
Output is correct |
2 |
Correct |
39 ms |
6784 KB |
Output is correct |
3 |
Correct |
39 ms |
6384 KB |
Output is correct |
4 |
Correct |
40 ms |
6824 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
5452 KB |
Output is correct |
5 |
Correct |
6 ms |
5512 KB |
Output is correct |
6 |
Correct |
5 ms |
5452 KB |
Output is correct |
7 |
Correct |
5 ms |
5196 KB |
Output is correct |
8 |
Correct |
6 ms |
5580 KB |
Output is correct |
9 |
Correct |
4 ms |
5452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
5452 KB |
Output is correct |
5 |
Correct |
6 ms |
5512 KB |
Output is correct |
6 |
Correct |
5 ms |
5452 KB |
Output is correct |
7 |
Correct |
5 ms |
5196 KB |
Output is correct |
8 |
Correct |
6 ms |
5580 KB |
Output is correct |
9 |
Correct |
4 ms |
5452 KB |
Output is correct |
10 |
Correct |
43 ms |
6820 KB |
Output is correct |
11 |
Correct |
39 ms |
6780 KB |
Output is correct |
12 |
Correct |
40 ms |
6748 KB |
Output is correct |
13 |
Correct |
40 ms |
8300 KB |
Output is correct |
14 |
Correct |
41 ms |
8520 KB |
Output is correct |
15 |
Correct |
39 ms |
8440 KB |
Output is correct |
16 |
Correct |
38 ms |
8080 KB |
Output is correct |
17 |
Correct |
38 ms |
8164 KB |
Output is correct |
18 |
Correct |
39 ms |
8440 KB |
Output is correct |
19 |
Correct |
36 ms |
8080 KB |
Output is correct |
20 |
Correct |
37 ms |
8204 KB |
Output is correct |
21 |
Correct |
39 ms |
8500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
5 ms |
5452 KB |
Output is correct |
5 |
Correct |
6 ms |
5512 KB |
Output is correct |
6 |
Correct |
5 ms |
5452 KB |
Output is correct |
7 |
Correct |
5 ms |
5196 KB |
Output is correct |
8 |
Correct |
6 ms |
5580 KB |
Output is correct |
9 |
Correct |
4 ms |
5452 KB |
Output is correct |
10 |
Correct |
5 ms |
5072 KB |
Output is correct |
11 |
Correct |
6 ms |
5512 KB |
Output is correct |
12 |
Correct |
5 ms |
5184 KB |
Output is correct |
13 |
Correct |
6 ms |
5488 KB |
Output is correct |
14 |
Correct |
6 ms |
5512 KB |
Output is correct |
15 |
Correct |
5 ms |
5452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
6764 KB |
Output is correct |
2 |
Correct |
39 ms |
6784 KB |
Output is correct |
3 |
Correct |
39 ms |
6384 KB |
Output is correct |
4 |
Correct |
40 ms |
6824 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
5 ms |
5452 KB |
Output is correct |
12 |
Correct |
6 ms |
5512 KB |
Output is correct |
13 |
Correct |
5 ms |
5452 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
6 ms |
5580 KB |
Output is correct |
16 |
Correct |
4 ms |
5452 KB |
Output is correct |
17 |
Correct |
43 ms |
6820 KB |
Output is correct |
18 |
Correct |
39 ms |
6780 KB |
Output is correct |
19 |
Correct |
40 ms |
6748 KB |
Output is correct |
20 |
Correct |
40 ms |
8300 KB |
Output is correct |
21 |
Correct |
41 ms |
8520 KB |
Output is correct |
22 |
Correct |
39 ms |
8440 KB |
Output is correct |
23 |
Correct |
38 ms |
8080 KB |
Output is correct |
24 |
Correct |
38 ms |
8164 KB |
Output is correct |
25 |
Correct |
39 ms |
8440 KB |
Output is correct |
26 |
Correct |
36 ms |
8080 KB |
Output is correct |
27 |
Correct |
37 ms |
8204 KB |
Output is correct |
28 |
Correct |
39 ms |
8500 KB |
Output is correct |
29 |
Correct |
5 ms |
5072 KB |
Output is correct |
30 |
Correct |
6 ms |
5512 KB |
Output is correct |
31 |
Correct |
5 ms |
5184 KB |
Output is correct |
32 |
Correct |
6 ms |
5488 KB |
Output is correct |
33 |
Correct |
6 ms |
5512 KB |
Output is correct |
34 |
Correct |
5 ms |
5452 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
40 ms |
7704 KB |
Output is correct |
37 |
Correct |
41 ms |
8172 KB |
Output is correct |
38 |
Correct |
40 ms |
8216 KB |
Output is correct |
39 |
Correct |
42 ms |
8532 KB |
Output is correct |
40 |
Correct |
41 ms |
8532 KB |
Output is correct |
41 |
Correct |
5 ms |
5708 KB |
Output is correct |
42 |
Correct |
38 ms |
8184 KB |
Output is correct |
43 |
Correct |
39 ms |
8428 KB |
Output is correct |
44 |
Correct |
39 ms |
8488 KB |
Output is correct |
45 |
Correct |
37 ms |
8204 KB |
Output is correct |
46 |
Correct |
38 ms |
8408 KB |
Output is correct |
47 |
Correct |
37 ms |
8416 KB |
Output is correct |