#include "dna.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct node{
int a1,t1,c1;
int a2,t2,c2;
int at,ac;
int ta,tc;
int ca,ct;
node(){
a1 = t1 = c1 = a2 = t2 = c2 = 0;
at = ac = ta = tc = ca = ct = 0;
}
};
node pre[N];
node add(node a,node b,int coef){
a.a1 += b.a1 * coef;
a.t1 += b.t1 * coef;
a.c1 += b.c1 * coef;
a.a2 += b.a2 * coef;
a.t2 += b.t2 * coef;
a.c2 += b.c2 * coef;
a.at += b.at * coef;
a.ac += b.ac * coef;
a.ta += b.ta * coef;
a.tc += b.tc * coef;
a.ca += b.ca * coef;
a.ct += b.ct * coef;
return a;
}
void init(string a, string b) {
int n = a.size();
for(int i = 0;i<n;i++){
if(a[i] == 'A'){
pre[i].a1++;
}
if(a[i] == 'T'){
pre[i].t1++;
}
if(a[i] == 'C'){
pre[i].c1++;
}
if(b[i] == 'A'){
pre[i].a2++;
}
if(b[i] == 'T'){
pre[i].t2++;
}
if(b[i] == 'C'){
pre[i].c2++;
}
if(a[i] == 'A' && b[i] == 'T'){
pre[i].at++;
}
if(a[i] == 'A' && b[i] == 'C'){
pre[i].ac++;
}
if(a[i] == 'T' && b[i] == 'A'){
pre[i].ta++;
}
if(a[i] == 'T' && b[i] == 'C'){
pre[i].tc++;
}
if(a[i] == 'C' && b[i] == 'A'){
pre[i].ca++;
}
if(a[i] == 'C' && b[i] == 'T'){
pre[i].ct++;
}
if(i){
pre[i] = add(pre[i],pre[i-1],1);
}
}
}
int get_distance(int x, int y) {
node val = pre[y];
if(x){
val = add(val,pre[x-1],-1);
}
if(val.a1 != val.a2 || val.t1 != val.t2 || val.c1 != val.c2){
return -1;
}
int ans = 0;
int mini = -1;
mini = min(val.at,val.ta);
ans += mini;
val.at -= mini;
val.ta -= mini;
mini = min(val.ac,val.ca);
ans += mini;
val.ac -= mini;
val.ca -= mini;
mini = min(val.tc,val.ct);
ans += mini;
val.tc -= mini;
val.ct -= mini;
ans += max(val.at,val.ac)*2;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
8204 KB |
Output is correct |
2 |
Correct |
39 ms |
8180 KB |
Output is correct |
3 |
Correct |
35 ms |
8048 KB |
Output is correct |
4 |
Correct |
37 ms |
8140 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4904 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
7 ms |
5684 KB |
Output is correct |
5 |
Correct |
8 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5760 KB |
Output is correct |
7 |
Correct |
9 ms |
5716 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4904 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
7 ms |
5684 KB |
Output is correct |
5 |
Correct |
8 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5760 KB |
Output is correct |
7 |
Correct |
9 ms |
5716 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
39 ms |
8200 KB |
Output is correct |
11 |
Correct |
38 ms |
8232 KB |
Output is correct |
12 |
Correct |
38 ms |
8476 KB |
Output is correct |
13 |
Correct |
46 ms |
8544 KB |
Output is correct |
14 |
Correct |
48 ms |
8516 KB |
Output is correct |
15 |
Correct |
34 ms |
8428 KB |
Output is correct |
16 |
Correct |
33 ms |
8420 KB |
Output is correct |
17 |
Correct |
58 ms |
8468 KB |
Output is correct |
18 |
Correct |
36 ms |
8392 KB |
Output is correct |
19 |
Correct |
36 ms |
8376 KB |
Output is correct |
20 |
Correct |
34 ms |
8400 KB |
Output is correct |
21 |
Correct |
31 ms |
8520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4904 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
7 ms |
5684 KB |
Output is correct |
5 |
Correct |
8 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5760 KB |
Output is correct |
7 |
Correct |
9 ms |
5716 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
5 ms |
5716 KB |
Output is correct |
10 |
Correct |
7 ms |
5716 KB |
Output is correct |
11 |
Correct |
6 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5672 KB |
Output is correct |
13 |
Correct |
10 ms |
5716 KB |
Output is correct |
14 |
Correct |
6 ms |
5716 KB |
Output is correct |
15 |
Correct |
6 ms |
5716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
8204 KB |
Output is correct |
2 |
Correct |
39 ms |
8180 KB |
Output is correct |
3 |
Correct |
35 ms |
8048 KB |
Output is correct |
4 |
Correct |
37 ms |
8140 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
4 ms |
4904 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
7 ms |
5684 KB |
Output is correct |
12 |
Correct |
8 ms |
5716 KB |
Output is correct |
13 |
Correct |
6 ms |
5760 KB |
Output is correct |
14 |
Correct |
9 ms |
5716 KB |
Output is correct |
15 |
Correct |
7 ms |
5716 KB |
Output is correct |
16 |
Correct |
5 ms |
5716 KB |
Output is correct |
17 |
Correct |
39 ms |
8200 KB |
Output is correct |
18 |
Correct |
38 ms |
8232 KB |
Output is correct |
19 |
Correct |
38 ms |
8476 KB |
Output is correct |
20 |
Correct |
46 ms |
8544 KB |
Output is correct |
21 |
Correct |
48 ms |
8516 KB |
Output is correct |
22 |
Correct |
34 ms |
8428 KB |
Output is correct |
23 |
Correct |
33 ms |
8420 KB |
Output is correct |
24 |
Correct |
58 ms |
8468 KB |
Output is correct |
25 |
Correct |
36 ms |
8392 KB |
Output is correct |
26 |
Correct |
36 ms |
8376 KB |
Output is correct |
27 |
Correct |
34 ms |
8400 KB |
Output is correct |
28 |
Correct |
31 ms |
8520 KB |
Output is correct |
29 |
Correct |
7 ms |
5716 KB |
Output is correct |
30 |
Correct |
6 ms |
5716 KB |
Output is correct |
31 |
Correct |
6 ms |
5672 KB |
Output is correct |
32 |
Correct |
10 ms |
5716 KB |
Output is correct |
33 |
Correct |
6 ms |
5716 KB |
Output is correct |
34 |
Correct |
6 ms |
5716 KB |
Output is correct |
35 |
Correct |
2 ms |
4996 KB |
Output is correct |
36 |
Correct |
35 ms |
8088 KB |
Output is correct |
37 |
Correct |
44 ms |
8236 KB |
Output is correct |
38 |
Correct |
45 ms |
8456 KB |
Output is correct |
39 |
Correct |
70 ms |
8476 KB |
Output is correct |
40 |
Correct |
65 ms |
8536 KB |
Output is correct |
41 |
Correct |
6 ms |
5784 KB |
Output is correct |
42 |
Correct |
38 ms |
8380 KB |
Output is correct |
43 |
Correct |
38 ms |
8400 KB |
Output is correct |
44 |
Correct |
33 ms |
8524 KB |
Output is correct |
45 |
Correct |
32 ms |
8424 KB |
Output is correct |
46 |
Correct |
34 ms |
8512 KB |
Output is correct |
47 |
Correct |
50 ms |
8488 KB |
Output is correct |