#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> ac, ca, at, ta, ct, tc;
void init(string a, string b) {
n = a.length();
ac.assign(n+1, 0);
ca.assign(n+1, 0);
at.assign(n+1, 0);
ta.assign(n+1, 0);
ct.assign(n+1, 0);
tc.assign(n+1, 0);
for(int i = 0; i < n; i++){
if(a[i] == 'A' && b[i] == 'C')ac[i+1]++;
if(a[i] == 'C' && b[i] == 'A')ca[i+1]++;
if(a[i] == 'A' && b[i] == 'T')at[i+1]++;
if(a[i] == 'T' && b[i] == 'A')ta[i+1]++;
if(a[i] == 'C' && b[i] == 'T')ct[i+1]++;
if(a[i] == 'T' && b[i] == 'C')tc[i+1]++;
ac[i+1] += ac[i];
ca[i+1] += ca[i];
at[i+1] += at[i];
ta[i+1] += ta[i];
ct[i+1] += ct[i];
tc[i+1] += tc[i];
}
}
int get_distance(int x, int y) {
int o_ac = ac[y+1]-ac[x];
int o_ca = ca[y+1]-ca[x];
int o_at = at[y+1]-at[x];
int o_ta = ta[y+1]-ta[x];
int o_ct = ct[y+1]-ct[x];
int o_tc = tc[y+1]-tc[x];
int ans = 0;
int curr;
curr = min(o_ac, o_ca);
ans += curr;
o_ac -= curr; o_ca -= curr;
curr = min(o_at, o_ta);
ans += curr;
o_at -= curr; o_ta -= curr;
curr = min(o_ct, o_tc);
ans += curr;
o_ct -= curr; o_tc -= curr;
curr = min(o_ac, min(o_ct, o_ta));
ans += curr*2;
o_ac -= curr; o_ct -= curr; o_ta -= curr;
curr = min(o_ca, min(o_tc, o_at));
ans += curr*2;
o_ca -= curr; o_tc -= curr; o_at -= curr;
if(o_ac || o_ca || o_at || o_ta || o_ct || o_tc)return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
5772 KB |
Output is correct |
2 |
Correct |
25 ms |
5868 KB |
Output is correct |
3 |
Correct |
25 ms |
5540 KB |
Output is correct |
4 |
Correct |
25 ms |
5896 KB |
Output is correct |
5 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3412 KB |
Output is correct |
5 |
Correct |
3 ms |
3384 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
4 ms |
3412 KB |
Output is correct |
9 |
Correct |
3 ms |
3376 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 |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3412 KB |
Output is correct |
5 |
Correct |
3 ms |
3384 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
4 ms |
3412 KB |
Output is correct |
9 |
Correct |
3 ms |
3376 KB |
Output is correct |
10 |
Correct |
26 ms |
5860 KB |
Output is correct |
11 |
Correct |
25 ms |
5896 KB |
Output is correct |
12 |
Correct |
27 ms |
5912 KB |
Output is correct |
13 |
Correct |
27 ms |
5996 KB |
Output is correct |
14 |
Correct |
27 ms |
6180 KB |
Output is correct |
15 |
Correct |
26 ms |
6184 KB |
Output is correct |
16 |
Correct |
25 ms |
5860 KB |
Output is correct |
17 |
Correct |
26 ms |
6036 KB |
Output is correct |
18 |
Correct |
26 ms |
6152 KB |
Output is correct |
19 |
Correct |
24 ms |
5912 KB |
Output is correct |
20 |
Correct |
25 ms |
6008 KB |
Output is correct |
21 |
Correct |
25 ms |
6152 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 |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
3412 KB |
Output is correct |
5 |
Correct |
3 ms |
3384 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
4 ms |
3412 KB |
Output is correct |
9 |
Correct |
3 ms |
3376 KB |
Output is correct |
10 |
Correct |
3 ms |
3156 KB |
Output is correct |
11 |
Correct |
4 ms |
3412 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
4 ms |
3412 KB |
Output is correct |
14 |
Correct |
4 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
5772 KB |
Output is correct |
2 |
Correct |
25 ms |
5868 KB |
Output is correct |
3 |
Correct |
25 ms |
5540 KB |
Output is correct |
4 |
Correct |
25 ms |
5896 KB |
Output is correct |
5 |
Correct |
1 ms |
212 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 |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
3412 KB |
Output is correct |
12 |
Correct |
3 ms |
3384 KB |
Output is correct |
13 |
Correct |
3 ms |
3412 KB |
Output is correct |
14 |
Correct |
3 ms |
3156 KB |
Output is correct |
15 |
Correct |
4 ms |
3412 KB |
Output is correct |
16 |
Correct |
3 ms |
3376 KB |
Output is correct |
17 |
Correct |
26 ms |
5860 KB |
Output is correct |
18 |
Correct |
25 ms |
5896 KB |
Output is correct |
19 |
Correct |
27 ms |
5912 KB |
Output is correct |
20 |
Correct |
27 ms |
5996 KB |
Output is correct |
21 |
Correct |
27 ms |
6180 KB |
Output is correct |
22 |
Correct |
26 ms |
6184 KB |
Output is correct |
23 |
Correct |
25 ms |
5860 KB |
Output is correct |
24 |
Correct |
26 ms |
6036 KB |
Output is correct |
25 |
Correct |
26 ms |
6152 KB |
Output is correct |
26 |
Correct |
24 ms |
5912 KB |
Output is correct |
27 |
Correct |
25 ms |
6008 KB |
Output is correct |
28 |
Correct |
25 ms |
6152 KB |
Output is correct |
29 |
Correct |
3 ms |
3156 KB |
Output is correct |
30 |
Correct |
4 ms |
3412 KB |
Output is correct |
31 |
Correct |
3 ms |
3156 KB |
Output is correct |
32 |
Correct |
4 ms |
3412 KB |
Output is correct |
33 |
Correct |
4 ms |
3412 KB |
Output is correct |
34 |
Correct |
3 ms |
3412 KB |
Output is correct |
35 |
Correct |
1 ms |
256 KB |
Output is correct |
36 |
Correct |
25 ms |
5628 KB |
Output is correct |
37 |
Correct |
25 ms |
5896 KB |
Output is correct |
38 |
Correct |
28 ms |
6036 KB |
Output is correct |
39 |
Correct |
32 ms |
6248 KB |
Output is correct |
40 |
Correct |
27 ms |
6152 KB |
Output is correct |
41 |
Correct |
3 ms |
3412 KB |
Output is correct |
42 |
Correct |
26 ms |
5912 KB |
Output is correct |
43 |
Correct |
25 ms |
6160 KB |
Output is correct |
44 |
Correct |
28 ms |
6176 KB |
Output is correct |
45 |
Correct |
26 ms |
5916 KB |
Output is correct |
46 |
Correct |
24 ms |
6160 KB |
Output is correct |
47 |
Correct |
31 ms |
6116 KB |
Output is correct |