#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
#define lim 100005
int n;
int pre_a_a[lim],pre_b_a[lim];// a string a char ----- b string a char
int pre_a_t[lim],pre_b_t[lim];// a string t char ----- b string t char
int pre_a_c[lim],pre_b_c[lim];// a string c char ----- b string c char
int at[lim],ta[lim],ac[lim],ca[lim],tc[lim],ct[lim];
int sum[lim];
inline bool querya(int x,int y){
if(pre_a_a[y+1]-pre_a_a[x]==pre_b_a[y+1]-pre_b_a[x])return 1;
return 0;
}
inline bool queryt(int x,int y){
if(pre_a_t[y+1]-pre_a_t[x]==pre_b_t[y+1]-pre_b_t[x])return 1;
return 0;
}
inline bool queryc(int x,int y){
if(pre_a_c[y+1]-pre_a_c[x]==pre_b_c[y+1]-pre_b_c[x])return 1;
return 0;
}
void init(string a,string b) {
n=a.length();
for(int i=0;i<n;i++){
pre_a_a[i+1]=pre_a_a[i];
if(a[i]=='A')pre_a_a[i+1]++;
pre_b_a[i+1]=pre_b_a[i];
if(b[i]=='A')pre_b_a[i+1]++;
pre_a_t[i+1]=pre_a_t[i];
if(a[i]=='T')pre_a_t[i+1]++;
pre_b_t[i+1]=pre_b_t[i];
if(b[i]=='T')pre_b_t[i+1]++;
pre_a_c[i+1]=pre_a_c[i];
if(a[i]=='C')pre_a_c[i+1]++;
pre_b_c[i+1]=pre_b_c[i];
if(b[i]=='C')pre_b_c[i+1]++;
sum[i+1]=sum[i];
if(a[i]!=b[i])sum[i+1]++;
ac[i+1]=ac[i],at[i+1]=at[i];
ca[i+1]=ca[i],ct[i+1]=ct[i];
ta[i+1]=ta[i],tc[i+1]=tc[i];
if(a[i]=='A'){
if(b[i]=='C')ac[i+1]++;
else if(b[i]=='T')at[i+1]++;
}
else if(a[i]=='C'){
if(b[i]=='A')ca[i+1]++;
else if(b[i]=='T')ct[i+1]++;
}
else{
if(b[i]=='A')ta[i+1]++;
else if(b[i]=='C')tc[i+1]++;
}
}
}
int get_distance(int x, int y) {
if(querya(x,y) && queryt(x,y) && queryc(x,y)){
int cev=0;
int anormal=sum[y+1]-sum[x];
cev+=min(at[y+1]-at[x],ta[y+1]-ta[x]);
cev+=min(ac[y+1]-ac[x],ca[y+1]-ca[x]);
cev+=min(tc[y+1]-tc[x],ct[y+1]-ct[x]);
anormal-=cev*2;
cev+=(anormal/3)*2;
return cev;
}
else return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
7260 KB |
Output is correct |
2 |
Correct |
27 ms |
7512 KB |
Output is correct |
3 |
Correct |
27 ms |
6948 KB |
Output is correct |
4 |
Correct |
36 ms |
7268 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
4 ms |
5980 KB |
Output is correct |
5 |
Correct |
4 ms |
5980 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
5748 KB |
Output is correct |
8 |
Correct |
5 ms |
6052 KB |
Output is correct |
9 |
Correct |
4 ms |
6232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
4 ms |
5980 KB |
Output is correct |
5 |
Correct |
4 ms |
5980 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
5748 KB |
Output is correct |
8 |
Correct |
5 ms |
6052 KB |
Output is correct |
9 |
Correct |
4 ms |
6232 KB |
Output is correct |
10 |
Correct |
28 ms |
7952 KB |
Output is correct |
11 |
Correct |
31 ms |
8036 KB |
Output is correct |
12 |
Correct |
29 ms |
8140 KB |
Output is correct |
13 |
Correct |
30 ms |
8216 KB |
Output is correct |
14 |
Correct |
29 ms |
8464 KB |
Output is correct |
15 |
Correct |
35 ms |
7788 KB |
Output is correct |
16 |
Correct |
35 ms |
8228 KB |
Output is correct |
17 |
Correct |
28 ms |
7988 KB |
Output is correct |
18 |
Correct |
28 ms |
8460 KB |
Output is correct |
19 |
Correct |
27 ms |
8544 KB |
Output is correct |
20 |
Correct |
28 ms |
8548 KB |
Output is correct |
21 |
Correct |
27 ms |
8460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
4 ms |
5980 KB |
Output is correct |
5 |
Correct |
4 ms |
5980 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
5748 KB |
Output is correct |
8 |
Correct |
5 ms |
6052 KB |
Output is correct |
9 |
Correct |
4 ms |
6232 KB |
Output is correct |
10 |
Correct |
5 ms |
5720 KB |
Output is correct |
11 |
Correct |
5 ms |
6236 KB |
Output is correct |
12 |
Correct |
5 ms |
5836 KB |
Output is correct |
13 |
Correct |
5 ms |
6236 KB |
Output is correct |
14 |
Correct |
6 ms |
5976 KB |
Output is correct |
15 |
Correct |
5 ms |
6232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
7260 KB |
Output is correct |
2 |
Correct |
27 ms |
7512 KB |
Output is correct |
3 |
Correct |
27 ms |
6948 KB |
Output is correct |
4 |
Correct |
36 ms |
7268 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
4 ms |
5980 KB |
Output is correct |
12 |
Correct |
4 ms |
5980 KB |
Output is correct |
13 |
Correct |
4 ms |
5980 KB |
Output is correct |
14 |
Correct |
4 ms |
5748 KB |
Output is correct |
15 |
Correct |
5 ms |
6052 KB |
Output is correct |
16 |
Correct |
4 ms |
6232 KB |
Output is correct |
17 |
Correct |
28 ms |
7952 KB |
Output is correct |
18 |
Correct |
31 ms |
8036 KB |
Output is correct |
19 |
Correct |
29 ms |
8140 KB |
Output is correct |
20 |
Correct |
30 ms |
8216 KB |
Output is correct |
21 |
Correct |
29 ms |
8464 KB |
Output is correct |
22 |
Correct |
35 ms |
7788 KB |
Output is correct |
23 |
Correct |
35 ms |
8228 KB |
Output is correct |
24 |
Correct |
28 ms |
7988 KB |
Output is correct |
25 |
Correct |
28 ms |
8460 KB |
Output is correct |
26 |
Correct |
27 ms |
8544 KB |
Output is correct |
27 |
Correct |
28 ms |
8548 KB |
Output is correct |
28 |
Correct |
27 ms |
8460 KB |
Output is correct |
29 |
Correct |
5 ms |
5720 KB |
Output is correct |
30 |
Correct |
5 ms |
6236 KB |
Output is correct |
31 |
Correct |
5 ms |
5836 KB |
Output is correct |
32 |
Correct |
5 ms |
6236 KB |
Output is correct |
33 |
Correct |
6 ms |
5976 KB |
Output is correct |
34 |
Correct |
5 ms |
6232 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
30 ms |
7776 KB |
Output is correct |
37 |
Correct |
31 ms |
8304 KB |
Output is correct |
38 |
Correct |
30 ms |
8204 KB |
Output is correct |
39 |
Correct |
37 ms |
8308 KB |
Output is correct |
40 |
Correct |
34 ms |
8680 KB |
Output is correct |
41 |
Correct |
4 ms |
6232 KB |
Output is correct |
42 |
Correct |
28 ms |
8312 KB |
Output is correct |
43 |
Correct |
33 ms |
8600 KB |
Output is correct |
44 |
Correct |
30 ms |
8580 KB |
Output is correct |
45 |
Correct |
33 ms |
8364 KB |
Output is correct |
46 |
Correct |
29 ms |
8968 KB |
Output is correct |
47 |
Correct |
33 ms |
8416 KB |
Output is correct |