#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
int n;
int cnta_s[100005];
int cntt_s[100005];
int cnta_t[100005];
int cntt_t[100005];
int cntat[100005];
int cntta[100005];
int cntac[100005];
int cntca[100005];
int cnttc[100005];
int cntct[100005];
void init(std::string s, std::string t) {
n=sz(s);
rep(x,0,n) cnta_s[x+1]=cnta_s[x]+(s[x]=='A');
rep(x,0,n) cntt_s[x+1]=cntt_s[x]+(s[x]=='T');
rep(x,0,n) cnta_t[x+1]=cnta_t[x]+(t[x]=='A');
rep(x,0,n) cntt_t[x+1]=cntt_t[x]+(t[x]=='T');
rep(x,0,n) cntat[x+1]=cntat[x]+(s[x]=='A' && t[x]=='T');
rep(x,0,n) cntta[x+1]=cntta[x]+(s[x]=='T' && t[x]=='A');
rep(x,0,n) cntac[x+1]=cntac[x]+(s[x]=='A' && t[x]=='C');
rep(x,0,n) cntca[x+1]=cntca[x]+(s[x]=='C' && t[x]=='A');
rep(x,0,n) cnttc[x+1]=cnttc[x]+(s[x]=='T' && t[x]=='C');
rep(x,0,n) cntct[x+1]=cntct[x]+(s[x]=='C' && t[x]=='T');
}
int get_distance(int l, int r) {
if (cnta_s[r+1]-cnta_s[l]!=cnta_t[r+1]-cnta_t[l]) return -1;
if (cntt_s[r+1]-cntt_s[l]!=cntt_t[r+1]-cntt_t[l]) return -1;
int at=cntat[r+1]-cntat[l];
int ta=cntta[r+1]-cntta[l];
int ac=cntac[r+1]-cntac[l];
int ca=cntca[r+1]-cntca[l];
int tc=cnttc[r+1]-cnttc[l];
int ct=cntct[r+1]-cntct[l];
//cout<<at<<" "<<ta<<" "<<ac<<" "<<ca<<" "<<tc<<" "<<ct<<endl;
int ans=0;
int temp;
temp=min(at,ta);
ans+=temp;
at-=temp,ta-=temp;
temp=min(ac,ca);
ans+=temp;
ac-=temp,ca-=temp;
temp=min(tc,ct);
ans+=temp;
tc-=temp,ct-=temp;
ans+=2*(at+ta);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
6020 KB |
Output is correct |
2 |
Correct |
45 ms |
6016 KB |
Output is correct |
3 |
Correct |
43 ms |
5744 KB |
Output is correct |
4 |
Correct |
50 ms |
6016 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
4684 KB |
Output is correct |
5 |
Correct |
11 ms |
4756 KB |
Output is correct |
6 |
Correct |
10 ms |
4684 KB |
Output is correct |
7 |
Correct |
11 ms |
4428 KB |
Output is correct |
8 |
Correct |
8 ms |
4684 KB |
Output is correct |
9 |
Correct |
8 ms |
4756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
4684 KB |
Output is correct |
5 |
Correct |
11 ms |
4756 KB |
Output is correct |
6 |
Correct |
10 ms |
4684 KB |
Output is correct |
7 |
Correct |
11 ms |
4428 KB |
Output is correct |
8 |
Correct |
8 ms |
4684 KB |
Output is correct |
9 |
Correct |
8 ms |
4756 KB |
Output is correct |
10 |
Correct |
51 ms |
6004 KB |
Output is correct |
11 |
Correct |
44 ms |
6016 KB |
Output is correct |
12 |
Correct |
45 ms |
6056 KB |
Output is correct |
13 |
Correct |
45 ms |
6272 KB |
Output is correct |
14 |
Correct |
44 ms |
6404 KB |
Output is correct |
15 |
Correct |
54 ms |
6396 KB |
Output is correct |
16 |
Correct |
46 ms |
6132 KB |
Output is correct |
17 |
Correct |
42 ms |
6272 KB |
Output is correct |
18 |
Correct |
43 ms |
6400 KB |
Output is correct |
19 |
Correct |
41 ms |
6128 KB |
Output is correct |
20 |
Correct |
40 ms |
6376 KB |
Output is correct |
21 |
Correct |
40 ms |
6396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
4684 KB |
Output is correct |
5 |
Correct |
11 ms |
4756 KB |
Output is correct |
6 |
Correct |
10 ms |
4684 KB |
Output is correct |
7 |
Correct |
11 ms |
4428 KB |
Output is correct |
8 |
Correct |
8 ms |
4684 KB |
Output is correct |
9 |
Correct |
8 ms |
4756 KB |
Output is correct |
10 |
Correct |
8 ms |
4428 KB |
Output is correct |
11 |
Correct |
9 ms |
4728 KB |
Output is correct |
12 |
Correct |
8 ms |
4428 KB |
Output is correct |
13 |
Correct |
9 ms |
4664 KB |
Output is correct |
14 |
Correct |
8 ms |
4684 KB |
Output is correct |
15 |
Correct |
8 ms |
4684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
6020 KB |
Output is correct |
2 |
Correct |
45 ms |
6016 KB |
Output is correct |
3 |
Correct |
43 ms |
5744 KB |
Output is correct |
4 |
Correct |
50 ms |
6016 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
8 ms |
4684 KB |
Output is correct |
12 |
Correct |
11 ms |
4756 KB |
Output is correct |
13 |
Correct |
10 ms |
4684 KB |
Output is correct |
14 |
Correct |
11 ms |
4428 KB |
Output is correct |
15 |
Correct |
8 ms |
4684 KB |
Output is correct |
16 |
Correct |
8 ms |
4756 KB |
Output is correct |
17 |
Correct |
51 ms |
6004 KB |
Output is correct |
18 |
Correct |
44 ms |
6016 KB |
Output is correct |
19 |
Correct |
45 ms |
6056 KB |
Output is correct |
20 |
Correct |
45 ms |
6272 KB |
Output is correct |
21 |
Correct |
44 ms |
6404 KB |
Output is correct |
22 |
Correct |
54 ms |
6396 KB |
Output is correct |
23 |
Correct |
46 ms |
6132 KB |
Output is correct |
24 |
Correct |
42 ms |
6272 KB |
Output is correct |
25 |
Correct |
43 ms |
6400 KB |
Output is correct |
26 |
Correct |
41 ms |
6128 KB |
Output is correct |
27 |
Correct |
40 ms |
6376 KB |
Output is correct |
28 |
Correct |
40 ms |
6396 KB |
Output is correct |
29 |
Correct |
8 ms |
4428 KB |
Output is correct |
30 |
Correct |
9 ms |
4728 KB |
Output is correct |
31 |
Correct |
8 ms |
4428 KB |
Output is correct |
32 |
Correct |
9 ms |
4664 KB |
Output is correct |
33 |
Correct |
8 ms |
4684 KB |
Output is correct |
34 |
Correct |
8 ms |
4684 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
46 ms |
5740 KB |
Output is correct |
37 |
Correct |
48 ms |
6016 KB |
Output is correct |
38 |
Correct |
45 ms |
6124 KB |
Output is correct |
39 |
Correct |
44 ms |
6392 KB |
Output is correct |
40 |
Correct |
48 ms |
6436 KB |
Output is correct |
41 |
Correct |
9 ms |
4728 KB |
Output is correct |
42 |
Correct |
45 ms |
6184 KB |
Output is correct |
43 |
Correct |
43 ms |
6396 KB |
Output is correct |
44 |
Correct |
43 ms |
6400 KB |
Output is correct |
45 |
Correct |
41 ms |
6164 KB |
Output is correct |
46 |
Correct |
43 ms |
6536 KB |
Output is correct |
47 |
Correct |
41 ms |
6468 KB |
Output is correct |