#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
int n,ans;
int pref[MAXN][3],pref2[MAXN][3];
int pairs[MAXN][6];
int a,b,c,d,e,f,curr;
bool ok(int l,int r){
for(int i=0;i<3;i++){
if(pref[r][i]-pref[l-1][i] != pref2[r][i]-pref2[l-1][i])return false;
}
return true;
}
void init(string a, string b){
n=int(a.size());
for(int i=1;i<=n;i++){
if(a[i-1]=='A')pref[i][0]++;
if(a[i-1]=='T')pref[i][1]++;
if(a[i-1]=='C')pref[i][2]++;
if(b[i-1]=='A')pref2[i][0]++;
if(b[i-1]=='T')pref2[i][1]++;
if(b[i-1]=='C')pref2[i][2]++;
if(a[i-1]=='A' and b[i-1]=='T')pairs[i][0]++;
if(a[i-1]=='T' and b[i-1]=='A')pairs[i][1]++;
if(a[i-1]=='A' and b[i-1]=='C')pairs[i][2]++;
if(a[i-1]=='C' and b[i-1]=='A')pairs[i][3]++;
if(a[i-1]=='C' and b[i-1]=='T')pairs[i][4]++;
if(a[i-1]=='T' and b[i-1]=='C')pairs[i][5]++;
for(int f=0;f<3;f++){
pref[i][f]+=pref[i-1][f];
pref2[i][f]+=pref2[i-1][f];
}
for(int f=0;f<6;f++){
pairs[i][f]+=pairs[i-1][f];
}
}
}
int get_distance(int x, int y){
x++; y++;
if(!ok(x,y))return -1;
ans=0;
a=pairs[y][0]-pairs[x-1][0];
b=pairs[y][1]-pairs[x-1][1];
c=pairs[y][2]-pairs[x-1][2];
d=pairs[y][3]-pairs[x-1][3];
e=pairs[y][4]-pairs[x-1][4];
f=pairs[y][5]-pairs[x-1][5];
curr=min(a,b); ans+=curr;
a-=curr; b-=curr;
curr=min(c,d); ans+=curr;
c-=curr; d-=curr;
curr=min(e,f); ans+=curr;
e-=curr; f-=curr;
ans+=2*max(a,b);
return ans;
}
/*
int main(){
init("ATACAT", "ACTATA");
cout<<get_distance(1,3)<<"\n";
cout<<get_distance(4,5)<<"\n";
cout<<get_distance(3,5)<<"\n";
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
6804 KB |
Output is correct |
2 |
Correct |
27 ms |
6820 KB |
Output is correct |
3 |
Correct |
26 ms |
6348 KB |
Output is correct |
4 |
Correct |
28 ms |
8140 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
256 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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
5460 KB |
Output is correct |
5 |
Correct |
4 ms |
5588 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
4 ms |
5460 KB |
Output is correct |
5 |
Correct |
4 ms |
5588 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5568 KB |
Output is correct |
10 |
Correct |
28 ms |
6748 KB |
Output is correct |
11 |
Correct |
28 ms |
6784 KB |
Output is correct |
12 |
Correct |
27 ms |
6856 KB |
Output is correct |
13 |
Correct |
27 ms |
6940 KB |
Output is correct |
14 |
Correct |
28 ms |
7200 KB |
Output is correct |
15 |
Correct |
26 ms |
7124 KB |
Output is correct |
16 |
Correct |
31 ms |
6824 KB |
Output is correct |
17 |
Correct |
27 ms |
7028 KB |
Output is correct |
18 |
Correct |
33 ms |
7160 KB |
Output is correct |
19 |
Correct |
26 ms |
6896 KB |
Output is correct |
20 |
Correct |
26 ms |
7068 KB |
Output is correct |
21 |
Correct |
27 ms |
7292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
4 ms |
5460 KB |
Output is correct |
5 |
Correct |
4 ms |
5588 KB |
Output is correct |
6 |
Correct |
4 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5568 KB |
Output is correct |
10 |
Correct |
6 ms |
5092 KB |
Output is correct |
11 |
Correct |
5 ms |
5716 KB |
Output is correct |
12 |
Correct |
5 ms |
5332 KB |
Output is correct |
13 |
Correct |
5 ms |
5716 KB |
Output is correct |
14 |
Correct |
5 ms |
5728 KB |
Output is correct |
15 |
Correct |
4 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
6804 KB |
Output is correct |
2 |
Correct |
27 ms |
6820 KB |
Output is correct |
3 |
Correct |
26 ms |
6348 KB |
Output is correct |
4 |
Correct |
28 ms |
8140 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 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 |
4 ms |
5460 KB |
Output is correct |
12 |
Correct |
4 ms |
5588 KB |
Output is correct |
13 |
Correct |
4 ms |
5460 KB |
Output is correct |
14 |
Correct |
4 ms |
5204 KB |
Output is correct |
15 |
Correct |
4 ms |
5588 KB |
Output is correct |
16 |
Correct |
3 ms |
5568 KB |
Output is correct |
17 |
Correct |
28 ms |
6748 KB |
Output is correct |
18 |
Correct |
28 ms |
6784 KB |
Output is correct |
19 |
Correct |
27 ms |
6856 KB |
Output is correct |
20 |
Correct |
27 ms |
6940 KB |
Output is correct |
21 |
Correct |
28 ms |
7200 KB |
Output is correct |
22 |
Correct |
26 ms |
7124 KB |
Output is correct |
23 |
Correct |
31 ms |
6824 KB |
Output is correct |
24 |
Correct |
27 ms |
7028 KB |
Output is correct |
25 |
Correct |
33 ms |
7160 KB |
Output is correct |
26 |
Correct |
26 ms |
6896 KB |
Output is correct |
27 |
Correct |
26 ms |
7068 KB |
Output is correct |
28 |
Correct |
27 ms |
7292 KB |
Output is correct |
29 |
Correct |
6 ms |
5092 KB |
Output is correct |
30 |
Correct |
5 ms |
5716 KB |
Output is correct |
31 |
Correct |
5 ms |
5332 KB |
Output is correct |
32 |
Correct |
5 ms |
5716 KB |
Output is correct |
33 |
Correct |
5 ms |
5728 KB |
Output is correct |
34 |
Correct |
4 ms |
5716 KB |
Output is correct |
35 |
Correct |
1 ms |
308 KB |
Output is correct |
36 |
Correct |
28 ms |
7752 KB |
Output is correct |
37 |
Correct |
28 ms |
8204 KB |
Output is correct |
38 |
Correct |
28 ms |
8232 KB |
Output is correct |
39 |
Correct |
28 ms |
8592 KB |
Output is correct |
40 |
Correct |
28 ms |
8568 KB |
Output is correct |
41 |
Correct |
5 ms |
5716 KB |
Output is correct |
42 |
Correct |
28 ms |
8084 KB |
Output is correct |
43 |
Correct |
29 ms |
8496 KB |
Output is correct |
44 |
Correct |
28 ms |
8436 KB |
Output is correct |
45 |
Correct |
27 ms |
8176 KB |
Output is correct |
46 |
Correct |
27 ms |
8544 KB |
Output is correct |
47 |
Correct |
27 ms |
8500 KB |
Output is correct |