#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
int n;
int pref[100010][6]; //0 ab 1 ba 2 ac 3 ca 4 bc 5 cb
void init(std::string a, std::string b) {
n=a.size();
for(int i=0; i< n; i++){
for(int j=0; j< 6; j++)pref[i+1][j]=pref[i][j];
if(a[i]=='A'){
if(b[i]=='C'){
pref[i+1][0]++;
}
else if(b[i]=='T'){
pref[i+1][2]++;
}
}
else if(a[i]=='C'){
if(b[i]=='A'){
pref[i+1][1]++;
}
else if(b[i]=='T'){
pref[i+1][4]++;
}
}
else{
if(b[i]=='A'){
pref[i+1][3]++;
}
else if(b[i]=='C'){
pref[i+1][5]++;
}
}
}
}
int get_distance(int x, int y) {
int ab, ba, ac, ca, bc, cb;
ab=pref[y+1][0]-pref[x][0];
ba=pref[y+1][1]-pref[x][1];
ac=pref[y+1][2]-pref[x][2];
ca=pref[y+1][3]-pref[x][3];
bc=pref[y+1][4]-pref[x][4];
cb=pref[y+1][5]-pref[x][5];
if(ab+ac!=ba+ca || ba+bc !=ab+cb || ca+cb!=ac+bc){
return -1;
}
else{
int ans=0;
int ab1=min(ab, ba);
int ac1=min(ac, ca);
int bc1=min(bc, cb);
ans+=ab1+ac1+bc1;
ab-=ab1; ba-=ab1;
return ans+max(ab, ba)*2;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4492 KB |
Output is correct |
2 |
Correct |
25 ms |
4492 KB |
Output is correct |
3 |
Correct |
27 ms |
4212 KB |
Output is correct |
4 |
Correct |
25 ms |
5800 KB |
Output is correct |
5 |
Correct |
0 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
5 |
Correct |
4 ms |
3156 KB |
Output is correct |
6 |
Correct |
4 ms |
3156 KB |
Output is correct |
7 |
Correct |
4 ms |
3028 KB |
Output is correct |
8 |
Correct |
3 ms |
3156 KB |
Output is correct |
9 |
Correct |
2 ms |
3216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
5 |
Correct |
4 ms |
3156 KB |
Output is correct |
6 |
Correct |
4 ms |
3156 KB |
Output is correct |
7 |
Correct |
4 ms |
3028 KB |
Output is correct |
8 |
Correct |
3 ms |
3156 KB |
Output is correct |
9 |
Correct |
2 ms |
3216 KB |
Output is correct |
10 |
Correct |
23 ms |
4480 KB |
Output is correct |
11 |
Correct |
26 ms |
4484 KB |
Output is correct |
12 |
Correct |
25 ms |
4676 KB |
Output is correct |
13 |
Correct |
29 ms |
4728 KB |
Output is correct |
14 |
Correct |
26 ms |
4888 KB |
Output is correct |
15 |
Correct |
26 ms |
4804 KB |
Output is correct |
16 |
Correct |
24 ms |
4676 KB |
Output is correct |
17 |
Correct |
30 ms |
4692 KB |
Output is correct |
18 |
Correct |
28 ms |
4788 KB |
Output is correct |
19 |
Correct |
24 ms |
4732 KB |
Output is correct |
20 |
Correct |
27 ms |
4732 KB |
Output is correct |
21 |
Correct |
29 ms |
4848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
5 |
Correct |
4 ms |
3156 KB |
Output is correct |
6 |
Correct |
4 ms |
3156 KB |
Output is correct |
7 |
Correct |
4 ms |
3028 KB |
Output is correct |
8 |
Correct |
3 ms |
3156 KB |
Output is correct |
9 |
Correct |
2 ms |
3216 KB |
Output is correct |
10 |
Correct |
3 ms |
2900 KB |
Output is correct |
11 |
Correct |
4 ms |
3388 KB |
Output is correct |
12 |
Correct |
4 ms |
3132 KB |
Output is correct |
13 |
Correct |
4 ms |
3392 KB |
Output is correct |
14 |
Correct |
5 ms |
3412 KB |
Output is correct |
15 |
Correct |
4 ms |
3388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4492 KB |
Output is correct |
2 |
Correct |
25 ms |
4492 KB |
Output is correct |
3 |
Correct |
27 ms |
4212 KB |
Output is correct |
4 |
Correct |
25 ms |
5800 KB |
Output is correct |
5 |
Correct |
0 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
4 ms |
3156 KB |
Output is correct |
13 |
Correct |
4 ms |
3156 KB |
Output is correct |
14 |
Correct |
4 ms |
3028 KB |
Output is correct |
15 |
Correct |
3 ms |
3156 KB |
Output is correct |
16 |
Correct |
2 ms |
3216 KB |
Output is correct |
17 |
Correct |
23 ms |
4480 KB |
Output is correct |
18 |
Correct |
26 ms |
4484 KB |
Output is correct |
19 |
Correct |
25 ms |
4676 KB |
Output is correct |
20 |
Correct |
29 ms |
4728 KB |
Output is correct |
21 |
Correct |
26 ms |
4888 KB |
Output is correct |
22 |
Correct |
26 ms |
4804 KB |
Output is correct |
23 |
Correct |
24 ms |
4676 KB |
Output is correct |
24 |
Correct |
30 ms |
4692 KB |
Output is correct |
25 |
Correct |
28 ms |
4788 KB |
Output is correct |
26 |
Correct |
24 ms |
4732 KB |
Output is correct |
27 |
Correct |
27 ms |
4732 KB |
Output is correct |
28 |
Correct |
29 ms |
4848 KB |
Output is correct |
29 |
Correct |
3 ms |
2900 KB |
Output is correct |
30 |
Correct |
4 ms |
3388 KB |
Output is correct |
31 |
Correct |
4 ms |
3132 KB |
Output is correct |
32 |
Correct |
4 ms |
3392 KB |
Output is correct |
33 |
Correct |
5 ms |
3412 KB |
Output is correct |
34 |
Correct |
4 ms |
3388 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
26 ms |
5604 KB |
Output is correct |
37 |
Correct |
28 ms |
5828 KB |
Output is correct |
38 |
Correct |
25 ms |
6068 KB |
Output is correct |
39 |
Correct |
29 ms |
6128 KB |
Output is correct |
40 |
Correct |
26 ms |
6160 KB |
Output is correct |
41 |
Correct |
3 ms |
3388 KB |
Output is correct |
42 |
Correct |
27 ms |
5868 KB |
Output is correct |
43 |
Correct |
25 ms |
6164 KB |
Output is correct |
44 |
Correct |
27 ms |
6128 KB |
Output is correct |
45 |
Correct |
27 ms |
5992 KB |
Output is correct |
46 |
Correct |
24 ms |
6140 KB |
Output is correct |
47 |
Correct |
24 ms |
6132 KB |
Output is correct |