#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define inf LLONG_MAX
#define pll pair<ll,ll>
#define pb push_back
// O n*q
ll asum[3][100005]={},bsum[3][100005]={},indeg[3][3][100005]={};
ll n;
string aa,bb;
int turn(char c){
if(c=='A')return 0;
if(c=='C')return 1;
return 2;
}
void init(std::string a, std::string b) {
n=a.size();
aa=a;
bb=b;
for(ll i=0;i<n;i++){
for(ll j=0;j<3;j++)asum[j][i+1]=asum[j][i];
for(ll j=0;j<3;j++)bsum[j][i+1]=bsum[j][i];
asum[turn(a[i])][i+1]++;
bsum[turn(b[i])][i+1]++;
}
for(ll i=0;i<n;i++){
for(ll j=0;j<3;j++){
for(ll k=0;k<3;k++)indeg[j][k][i+1]=indeg[j][k][i];
}
if(b[i]!=a[i]){
indeg[turn(b[i])][turn(a[i])][i+1]++;
}
}
}
ll l;
int get_distance(int x, int y) {
for(ll i=0;i<3;i++){
ll temp=asum[i][y+1]-asum[i][x],temp2=bsum[i][y+1]-bsum[i][x];
if(temp!=temp2)return -1;
}
ll ans=0;
ll buff[3][3]={};
for(ll i=0;i<3;i++){
for(ll j=0;j<3;j++){
buff[i][j]=indeg[i][j][y+1]-indeg[i][j][x];
}
}
for(ll i=0;i<3;i++){
for(ll j=0;j<3;j++){
if(i==j)continue;
ll temp=min(buff[i][j],buff[j][i]);
ans+=temp;
buff[i][j]-=temp;
buff[j][i]-=temp;
}
}
bool v=0;
if(buff[0][1]==buff[1][2]&&buff[1][2]==buff[2][0]){
v=1;ans+=2*buff[0][1];
}
if(buff[1][0]==buff[2][1]&&buff[0][2]==buff[2][1]){
v=1;ans+=2*buff[2][1];
}
if(v==0)return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
14016 KB |
Output is correct |
2 |
Correct |
57 ms |
14156 KB |
Output is correct |
3 |
Correct |
48 ms |
13088 KB |
Output is correct |
4 |
Correct |
51 ms |
15540 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
10 ms |
12628 KB |
Output is correct |
5 |
Correct |
9 ms |
12756 KB |
Output is correct |
6 |
Correct |
9 ms |
12756 KB |
Output is correct |
7 |
Correct |
10 ms |
11988 KB |
Output is correct |
8 |
Correct |
9 ms |
12756 KB |
Output is correct |
9 |
Correct |
8 ms |
12776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
10 ms |
12628 KB |
Output is correct |
5 |
Correct |
9 ms |
12756 KB |
Output is correct |
6 |
Correct |
9 ms |
12756 KB |
Output is correct |
7 |
Correct |
10 ms |
11988 KB |
Output is correct |
8 |
Correct |
9 ms |
12756 KB |
Output is correct |
9 |
Correct |
8 ms |
12776 KB |
Output is correct |
10 |
Correct |
53 ms |
14000 KB |
Output is correct |
11 |
Correct |
53 ms |
14120 KB |
Output is correct |
12 |
Correct |
62 ms |
13644 KB |
Output is correct |
13 |
Correct |
64 ms |
14000 KB |
Output is correct |
14 |
Correct |
63 ms |
14532 KB |
Output is correct |
15 |
Correct |
56 ms |
14412 KB |
Output is correct |
16 |
Correct |
51 ms |
13692 KB |
Output is correct |
17 |
Correct |
50 ms |
14004 KB |
Output is correct |
18 |
Correct |
52 ms |
14500 KB |
Output is correct |
19 |
Correct |
37 ms |
13712 KB |
Output is correct |
20 |
Correct |
38 ms |
14016 KB |
Output is correct |
21 |
Correct |
37 ms |
14540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
10 ms |
12628 KB |
Output is correct |
5 |
Correct |
9 ms |
12756 KB |
Output is correct |
6 |
Correct |
9 ms |
12756 KB |
Output is correct |
7 |
Correct |
10 ms |
11988 KB |
Output is correct |
8 |
Correct |
9 ms |
12756 KB |
Output is correct |
9 |
Correct |
8 ms |
12776 KB |
Output is correct |
10 |
Correct |
8 ms |
11800 KB |
Output is correct |
11 |
Correct |
10 ms |
12992 KB |
Output is correct |
12 |
Correct |
9 ms |
12132 KB |
Output is correct |
13 |
Correct |
11 ms |
12884 KB |
Output is correct |
14 |
Correct |
10 ms |
12988 KB |
Output is correct |
15 |
Correct |
9 ms |
13024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
14016 KB |
Output is correct |
2 |
Correct |
57 ms |
14156 KB |
Output is correct |
3 |
Correct |
48 ms |
13088 KB |
Output is correct |
4 |
Correct |
51 ms |
15540 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
10 ms |
12628 KB |
Output is correct |
12 |
Correct |
9 ms |
12756 KB |
Output is correct |
13 |
Correct |
9 ms |
12756 KB |
Output is correct |
14 |
Correct |
10 ms |
11988 KB |
Output is correct |
15 |
Correct |
9 ms |
12756 KB |
Output is correct |
16 |
Correct |
8 ms |
12776 KB |
Output is correct |
17 |
Correct |
53 ms |
14000 KB |
Output is correct |
18 |
Correct |
53 ms |
14120 KB |
Output is correct |
19 |
Correct |
62 ms |
13644 KB |
Output is correct |
20 |
Correct |
64 ms |
14000 KB |
Output is correct |
21 |
Correct |
63 ms |
14532 KB |
Output is correct |
22 |
Correct |
56 ms |
14412 KB |
Output is correct |
23 |
Correct |
51 ms |
13692 KB |
Output is correct |
24 |
Correct |
50 ms |
14004 KB |
Output is correct |
25 |
Correct |
52 ms |
14500 KB |
Output is correct |
26 |
Correct |
37 ms |
13712 KB |
Output is correct |
27 |
Correct |
38 ms |
14016 KB |
Output is correct |
28 |
Correct |
37 ms |
14540 KB |
Output is correct |
29 |
Correct |
8 ms |
11800 KB |
Output is correct |
30 |
Correct |
10 ms |
12992 KB |
Output is correct |
31 |
Correct |
9 ms |
12132 KB |
Output is correct |
32 |
Correct |
11 ms |
12884 KB |
Output is correct |
33 |
Correct |
10 ms |
12988 KB |
Output is correct |
34 |
Correct |
9 ms |
13024 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
54 ms |
14412 KB |
Output is correct |
37 |
Correct |
50 ms |
15544 KB |
Output is correct |
38 |
Correct |
61 ms |
15140 KB |
Output is correct |
39 |
Correct |
71 ms |
15852 KB |
Output is correct |
40 |
Correct |
62 ms |
15820 KB |
Output is correct |
41 |
Correct |
8 ms |
12992 KB |
Output is correct |
42 |
Correct |
49 ms |
15032 KB |
Output is correct |
43 |
Correct |
48 ms |
15800 KB |
Output is correct |
44 |
Correct |
53 ms |
15780 KB |
Output is correct |
45 |
Correct |
37 ms |
15036 KB |
Output is correct |
46 |
Correct |
38 ms |
15792 KB |
Output is correct |
47 |
Correct |
38 ms |
15720 KB |
Output is correct |