//#include "dna_ioi.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> aca, ata, ctc, aa, tt, cc;
void init(string a, string b)
{
//cout<<"alo"<<endl;
int n = a.size();
aca.resize(n+2, {0, 0});
ata.resize(n+2, {0, 0});
ctc.resize(n+2, {0, 0});
aa.resize(n+2, {0, 0});
cc.resize(n+2, {0, 0});
tt.resize(n+2, {0, 0});
for(int i = 1; i<=n; i++)
{
aca[i].first = aca[i-1].first;
aca[i].second = aca[i-1].second;
if(a[i-1] == 'A' && b[i-1] == 'C')aca[i].first++;
if(a[i-1] == 'C' && b[i-1] == 'A')aca[i].second++;
ata[i].first = ata[i-1].first;
ata[i].second = ata[i-1].second;
if(a[i-1] == 'A' && b[i-1] == 'T')ata[i].first++;
if(a[i-1] == 'T' && b[i-1] == 'A')ata[i].second++;
ctc[i].first = ctc[i-1].first;
ctc[i].second = ctc[i-1].second;
if(a[i-1] == 'T' && b[i-1] == 'C')ctc[i].first++;
if(a[i-1] == 'C' && b[i-1] == 'T')ctc[i].second++;
//
aa[i].first = aa[i-1].first;
aa[i].second = aa[i-1].second;
if(a[i-1] == 'A')aa[i].first++;
if(b[i-1] == 'A')aa[i].second++;
tt[i].first = tt[i-1].first;
tt[i].second = tt[i-1].second;
if(a[i-1] == 'T')tt[i].first++;
if(b[i-1] == 'T')tt[i].second++;
cc[i].first = cc[i-1].first;
cc[i].second = cc[i-1].second;
if(a[i-1] == 'C')cc[i].first++;
if(b[i-1] == 'C')cc[i].second++;
}
}
int get_distance(int x, int y)
{
x++;
y++;
//cout<<aa[y].first - aa[x-1].first<<" "<<aa[y].second - aa[x-1].second<<endl;
if(aa[y].first - aa[x-1].first == aa[y].second - aa[x-1].second && cc[y].first - cc[x-1].first == cc[y].second - cc[x-1].second && tt[y].first - tt[x-1].first == tt[y].second - tt[x-1].second)
{
long long ans = 0, sob = 0;
ans+=min(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second);
sob+=max(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second) - min(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second);
ans+=min(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second);
sob+=max(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second) - min(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second);
ans+=min(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second);
sob+=max(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second) - min(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second);
ans+=(sob/3)*2;
return ans;
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
8076 KB |
Output is correct |
2 |
Correct |
48 ms |
8168 KB |
Output is correct |
3 |
Correct |
38 ms |
7760 KB |
Output is correct |
4 |
Correct |
39 ms |
8200 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 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 |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
6 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5716 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5752 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 |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
6 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5716 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5752 KB |
Output is correct |
10 |
Correct |
40 ms |
8108 KB |
Output is correct |
11 |
Correct |
49 ms |
8200 KB |
Output is correct |
12 |
Correct |
35 ms |
8084 KB |
Output is correct |
13 |
Correct |
37 ms |
8340 KB |
Output is correct |
14 |
Correct |
34 ms |
8588 KB |
Output is correct |
15 |
Correct |
40 ms |
8504 KB |
Output is correct |
16 |
Correct |
33 ms |
8072 KB |
Output is correct |
17 |
Correct |
32 ms |
8156 KB |
Output is correct |
18 |
Correct |
32 ms |
8412 KB |
Output is correct |
19 |
Correct |
30 ms |
8048 KB |
Output is correct |
20 |
Correct |
44 ms |
8184 KB |
Output is correct |
21 |
Correct |
31 ms |
8428 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 |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
6 ms |
5716 KB |
Output is correct |
6 |
Correct |
6 ms |
5716 KB |
Output is correct |
7 |
Correct |
5 ms |
5332 KB |
Output is correct |
8 |
Correct |
7 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5752 KB |
Output is correct |
10 |
Correct |
6 ms |
5204 KB |
Output is correct |
11 |
Correct |
6 ms |
5692 KB |
Output is correct |
12 |
Correct |
5 ms |
5332 KB |
Output is correct |
13 |
Correct |
6 ms |
5676 KB |
Output is correct |
14 |
Correct |
7 ms |
5748 KB |
Output is correct |
15 |
Correct |
5 ms |
5736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
8076 KB |
Output is correct |
2 |
Correct |
48 ms |
8168 KB |
Output is correct |
3 |
Correct |
38 ms |
7760 KB |
Output is correct |
4 |
Correct |
39 ms |
8200 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5716 KB |
Output is correct |
13 |
Correct |
6 ms |
5716 KB |
Output is correct |
14 |
Correct |
5 ms |
5332 KB |
Output is correct |
15 |
Correct |
7 ms |
5716 KB |
Output is correct |
16 |
Correct |
4 ms |
5752 KB |
Output is correct |
17 |
Correct |
40 ms |
8108 KB |
Output is correct |
18 |
Correct |
49 ms |
8200 KB |
Output is correct |
19 |
Correct |
35 ms |
8084 KB |
Output is correct |
20 |
Correct |
37 ms |
8340 KB |
Output is correct |
21 |
Correct |
34 ms |
8588 KB |
Output is correct |
22 |
Correct |
40 ms |
8504 KB |
Output is correct |
23 |
Correct |
33 ms |
8072 KB |
Output is correct |
24 |
Correct |
32 ms |
8156 KB |
Output is correct |
25 |
Correct |
32 ms |
8412 KB |
Output is correct |
26 |
Correct |
30 ms |
8048 KB |
Output is correct |
27 |
Correct |
44 ms |
8184 KB |
Output is correct |
28 |
Correct |
31 ms |
8428 KB |
Output is correct |
29 |
Correct |
6 ms |
5204 KB |
Output is correct |
30 |
Correct |
6 ms |
5692 KB |
Output is correct |
31 |
Correct |
5 ms |
5332 KB |
Output is correct |
32 |
Correct |
6 ms |
5676 KB |
Output is correct |
33 |
Correct |
7 ms |
5748 KB |
Output is correct |
34 |
Correct |
5 ms |
5736 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
37 ms |
7644 KB |
Output is correct |
37 |
Correct |
38 ms |
8200 KB |
Output is correct |
38 |
Correct |
52 ms |
8276 KB |
Output is correct |
39 |
Correct |
37 ms |
8560 KB |
Output is correct |
40 |
Correct |
40 ms |
8540 KB |
Output is correct |
41 |
Correct |
6 ms |
5704 KB |
Output is correct |
42 |
Correct |
34 ms |
8084 KB |
Output is correct |
43 |
Correct |
35 ms |
8432 KB |
Output is correct |
44 |
Correct |
42 ms |
8436 KB |
Output is correct |
45 |
Correct |
34 ms |
8184 KB |
Output is correct |
46 |
Correct |
36 ms |
8524 KB |
Output is correct |
47 |
Correct |
51 ms |
8444 KB |
Output is correct |