#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
string a,b;
vector<vector<int> > leta,letb;
// ac ca at ta ct tc
// 0 1 2 3 4 5
vector<int> contac,contca,contat,contta,contct,conttc;
int get_comb(char up, char down){
if(up=='A' && down=='C') return 0;
if(up=='C' && down=='A') return 1;
if(up=='A' && down=='T') return 2;
if(up=='T' && down=='A') return 3;
if(up=='C' && down=='T') return 4;
return 5;
}
int get_letter(char act){
if(act=='A') return 0;
if(act=='T') return 1;
return 2;
}
void init(std::string A, std::string B) {
a=A;
b=B;
int n=a.size();
leta.resize(n,vector<int> (3,0));
letb.resize(n,vector<int> (3,0));
leta[0][get_letter(a[0])]++;
letb[0][get_letter(b[0])]++;
for(int i=1;i<n;i++){
for(int j=0;j<3;j++){
leta[i][j]=leta[i-1][j];
letb[i][j]=letb[i-1][j];
}
leta[i][get_letter(a[i])]++;
letb[i][get_letter(b[i])]++;
}
contac.push_back(0); contca.push_back(0);
contat.push_back(0); contta.push_back(0);
contct.push_back(0); conttc.push_back(0);
if(a[0]=='A' && b[0]=='C') contac[0]++;
if(a[0]=='C' && b[0]=='A') contca[0]++;
if(a[0]=='A' && b[0]=='T') contat[0]++;
if(a[0]=='T' && b[0]=='A') contta[0]++;
if(a[0]=='C' && b[0]=='T') contct[0]++;
if(a[0]=='T' && b[0]=='C') conttc[0]++;
for(int i=1;i<n;i++){
contac.push_back(contac[contac.size()-1]); contca.push_back(contca[contca.size()-1]);
contat.push_back(contat[contat.size()-1]); contta.push_back(contta[contta.size()-1]);
contct.push_back(contct[contct.size()-1]); conttc.push_back(conttc[conttc.size()-1]);
if(a[i]=='A' && b[i]=='C') contac[i]++;
if(a[i]=='C' && b[i]=='A') contca[i]++;
if(a[i]=='A' && b[i]=='T') contat[i]++;
if(a[i]=='T' && b[i]=='A') contta[i]++;
if(a[i]=='C' && b[i]=='T') contct[i]++;
if(a[i]=='T' && b[i]=='C') conttc[i]++;
}
}
int count_letter(bool is_a, int i, int j, int pos){
if(is_a)
return (i==0) ? leta[j][pos] : leta[j][pos] - leta[i-1][pos];
return (i==0) ? letb[j][pos] : letb[j][pos] - letb[i-1][pos];
}
/*
int count_comb(int i, int j, int pos){
return (i==0) ? cont[j][pos] : cont[j][pos] - cont[i-1][pos];
}
*/
void count(int &res, int &f, int &s){
res+=f;
s-=f;
f=0;
}
int get_distance(int x, int y) {
for(int i=0;i<3;i++)
if(count_letter(1,x,y,i)!=count_letter(0,x,y,i)) return -1;
int ac=(x==0) ? contac[y] : contac[y]-contac[x-1];
int ca=(x==0) ? contca[y] : contca[y]-contca[x-1];
int at=(x==0) ? contat[y] : contat[y]-contat[x-1];
int ta=(x==0) ? contta[y] : contta[y]-contta[x-1];
int ct=(x==0) ? contct[y] : contct[y]-contct[x-1];
int tc=(x==0) ? conttc[y] : conttc[y]-conttc[x-1];
int res=0;
(ac<ca) ? count(res,ac,ca) : count(res,ca,ac);
(at<ta) ? count(res,at,ta) : count(res,ta,at);
(tc<ct) ? count(res,tc,ct) : count(res,ct,tc);
ac=max(ac,ca);
at=max(at,ta);
tc=max(tc,ct);
res+=ac+at;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
16016 KB |
Output is correct |
2 |
Correct |
85 ms |
15992 KB |
Output is correct |
3 |
Correct |
81 ms |
14780 KB |
Output is correct |
4 |
Correct |
85 ms |
15972 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
23 ms |
14640 KB |
Output is correct |
5 |
Correct |
23 ms |
14660 KB |
Output is correct |
6 |
Correct |
24 ms |
14740 KB |
Output is correct |
7 |
Correct |
23 ms |
13892 KB |
Output is correct |
8 |
Correct |
24 ms |
14560 KB |
Output is correct |
9 |
Correct |
22 ms |
14560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
23 ms |
14640 KB |
Output is correct |
5 |
Correct |
23 ms |
14660 KB |
Output is correct |
6 |
Correct |
24 ms |
14740 KB |
Output is correct |
7 |
Correct |
23 ms |
13892 KB |
Output is correct |
8 |
Correct |
24 ms |
14560 KB |
Output is correct |
9 |
Correct |
22 ms |
14560 KB |
Output is correct |
10 |
Correct |
91 ms |
16016 KB |
Output is correct |
11 |
Correct |
84 ms |
15976 KB |
Output is correct |
12 |
Correct |
89 ms |
15584 KB |
Output is correct |
13 |
Correct |
89 ms |
15712 KB |
Output is correct |
14 |
Correct |
95 ms |
16364 KB |
Output is correct |
15 |
Correct |
86 ms |
16224 KB |
Output is correct |
16 |
Correct |
81 ms |
15524 KB |
Output is correct |
17 |
Correct |
81 ms |
15700 KB |
Output is correct |
18 |
Correct |
90 ms |
16332 KB |
Output is correct |
19 |
Correct |
59 ms |
15652 KB |
Output is correct |
20 |
Correct |
57 ms |
15812 KB |
Output is correct |
21 |
Correct |
59 ms |
16364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
23 ms |
14640 KB |
Output is correct |
5 |
Correct |
23 ms |
14660 KB |
Output is correct |
6 |
Correct |
24 ms |
14740 KB |
Output is correct |
7 |
Correct |
23 ms |
13892 KB |
Output is correct |
8 |
Correct |
24 ms |
14560 KB |
Output is correct |
9 |
Correct |
22 ms |
14560 KB |
Output is correct |
10 |
Correct |
22 ms |
13364 KB |
Output is correct |
11 |
Correct |
24 ms |
14608 KB |
Output is correct |
12 |
Correct |
22 ms |
13684 KB |
Output is correct |
13 |
Correct |
26 ms |
14920 KB |
Output is correct |
14 |
Correct |
25 ms |
14768 KB |
Output is correct |
15 |
Correct |
24 ms |
14776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
16016 KB |
Output is correct |
2 |
Correct |
85 ms |
15992 KB |
Output is correct |
3 |
Correct |
81 ms |
14780 KB |
Output is correct |
4 |
Correct |
85 ms |
15972 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
23 ms |
14640 KB |
Output is correct |
12 |
Correct |
23 ms |
14660 KB |
Output is correct |
13 |
Correct |
24 ms |
14740 KB |
Output is correct |
14 |
Correct |
23 ms |
13892 KB |
Output is correct |
15 |
Correct |
24 ms |
14560 KB |
Output is correct |
16 |
Correct |
22 ms |
14560 KB |
Output is correct |
17 |
Correct |
91 ms |
16016 KB |
Output is correct |
18 |
Correct |
84 ms |
15976 KB |
Output is correct |
19 |
Correct |
89 ms |
15584 KB |
Output is correct |
20 |
Correct |
89 ms |
15712 KB |
Output is correct |
21 |
Correct |
95 ms |
16364 KB |
Output is correct |
22 |
Correct |
86 ms |
16224 KB |
Output is correct |
23 |
Correct |
81 ms |
15524 KB |
Output is correct |
24 |
Correct |
81 ms |
15700 KB |
Output is correct |
25 |
Correct |
90 ms |
16332 KB |
Output is correct |
26 |
Correct |
59 ms |
15652 KB |
Output is correct |
27 |
Correct |
57 ms |
15812 KB |
Output is correct |
28 |
Correct |
59 ms |
16364 KB |
Output is correct |
29 |
Correct |
22 ms |
13364 KB |
Output is correct |
30 |
Correct |
24 ms |
14608 KB |
Output is correct |
31 |
Correct |
22 ms |
13684 KB |
Output is correct |
32 |
Correct |
26 ms |
14920 KB |
Output is correct |
33 |
Correct |
25 ms |
14768 KB |
Output is correct |
34 |
Correct |
24 ms |
14776 KB |
Output is correct |
35 |
Correct |
1 ms |
292 KB |
Output is correct |
36 |
Correct |
82 ms |
14844 KB |
Output is correct |
37 |
Correct |
84 ms |
16064 KB |
Output is correct |
38 |
Correct |
89 ms |
15612 KB |
Output is correct |
39 |
Correct |
88 ms |
16436 KB |
Output is correct |
40 |
Correct |
92 ms |
16492 KB |
Output is correct |
41 |
Correct |
22 ms |
14664 KB |
Output is correct |
42 |
Correct |
76 ms |
15612 KB |
Output is correct |
43 |
Correct |
90 ms |
16480 KB |
Output is correct |
44 |
Correct |
80 ms |
16492 KB |
Output is correct |
45 |
Correct |
60 ms |
15692 KB |
Output is correct |
46 |
Correct |
60 ms |
16460 KB |
Output is correct |
47 |
Correct |
60 ms |
16480 KB |
Output is correct |