#include "dna.h"
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
map<string, int> typ = {{"AT",0},{"AC",1},{"TA",2},{"TC",3},{"CA",4},{"CT",5},{"AA",6},{"TT",7},{"CC",8}};
map<char, int> znak = {{'A',0},{'T',1},{'C',2}};
int pref_typ[100001][9];
int pref_znak[100001][2][3];
int n;
void init(string s1, string s2)
{
n = (int)s1.size();
rep(i,n)
{
// cout << znak[s1[i]] << " znak s1\n";
rep(j,3)
{
if(znak[s1[i]] == j) pref_znak[i+1][0][znak[s1[i]]] = pref_znak[i][0][znak[s1[i]]] +1;
else pref_znak[i+1][0][j] = pref_znak[i][0][j];
}
}
rep(i,n)
{
rep(j,3)
{
if(znak[s2[i]] == j) pref_znak[i+1][1][znak[s2[i]]] = pref_znak[i][1][znak[s2[i]]] +1;
else pref_znak[i+1][1][j] = pref_znak[i][1][j];
}
}
rep(i,n)
{
rep(z,9)
{
string s; s += s1[i]; s+= s2[i];
if(typ[s] == z) pref_typ[i+1][z] = pref_typ[i][z] +1;
else pref_typ[i+1][z] = pref_typ[i][z];
}
}
}
int get_distance(int p, int k)
{
int T1 = pref_znak[k+1][0][znak['T']] - pref_znak[p][0][znak['T']];
int C1 = pref_znak[k+1][0][znak['C']] - pref_znak[p][0][znak['C']];
int A1 = pref_znak[k+1][0][znak['A']] - pref_znak[p][0][znak['A']];
int T2 = pref_znak[k+1][1][znak['T']] - pref_znak[p][1][znak['T']];
int C2 = pref_znak[k+1][1][znak['C']] - pref_znak[p][1][znak['C']];
int A2 = pref_znak[k+1][1][znak['A']] - pref_znak[p][1][znak['A']];
// cout << T1 << " " << C1 << " " << A1 << " " << T2 << " " << C2 << " " << A2 << " dane\n";
if(T1 != T2 || C1 != C2 || A1 != A2)
{
return -1;
}
int ust = k-p+1;
int ans = 0;
ust -= pref_typ[k+1][typ["AA"]] - pref_typ[p][typ["AA"]];
ust -= pref_typ[k+1][typ["TT"]] - pref_typ[p][typ["TT"]];
ust -= pref_typ[k+1][typ["CC"]] - pref_typ[p][typ["CC"]];
int AC = pref_typ[k+1][typ["AC"]] - pref_typ[p][typ["AC"]];
int AT = pref_typ[k+1][typ["AT"]] - pref_typ[p][typ["AT"]];
int CA = pref_typ[k+1][typ["CA"]] - pref_typ[p][typ["CA"]];
int CT = pref_typ[k+1][typ["CT"]] - pref_typ[p][typ["CT"]];
int TC = pref_typ[k+1][typ["TC"]] - pref_typ[p][typ["TC"]];
int TA = pref_typ[k+1][typ["TA"]] - pref_typ[p][typ["TA"]];
int pom;
//dwa
ust -= min(AC,CA)*2;
ans += min(AC,CA);
pom = min(AC,CA);
AC -= pom;
CA -= pom;
ust -= min(AT,TA)*2;
ans += min(AT,TA);
pom = min(TA,AT);
TA -= pom;
AT -= pom;
ust -= min(TC,CT)*2;
ans += min(TC,CT);
pom = min(TC,CT);
TC -= pom;
CT -= pom;
//trzy
ust -= min(min(AT,TC),CA)*3;
ans += min(min(AT,TC),CA)*2;
pom = min(min(AT,TC),CA);
AT -= pom;
TC -= pom;
CA -= pom;
ust -= min(min(AC,CT),TA)*3;
ans += min(min(AC,CT),TA)*2;
pom = min(min(AC,CT),TA);
AC -= pom;
CT -= pom;
TA -= pom;
return ans+max(0,ust-1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
7952 KB |
Output is correct |
2 |
Correct |
90 ms |
8016 KB |
Output is correct |
3 |
Correct |
92 ms |
7516 KB |
Output is correct |
4 |
Correct |
92 ms |
8184 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
6820 KB |
Output is correct |
5 |
Correct |
26 ms |
6748 KB |
Output is correct |
6 |
Correct |
26 ms |
6812 KB |
Output is correct |
7 |
Correct |
25 ms |
6236 KB |
Output is correct |
8 |
Correct |
31 ms |
6996 KB |
Output is correct |
9 |
Correct |
23 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
6820 KB |
Output is correct |
5 |
Correct |
26 ms |
6748 KB |
Output is correct |
6 |
Correct |
26 ms |
6812 KB |
Output is correct |
7 |
Correct |
25 ms |
6236 KB |
Output is correct |
8 |
Correct |
31 ms |
6996 KB |
Output is correct |
9 |
Correct |
23 ms |
6748 KB |
Output is correct |
10 |
Correct |
90 ms |
7992 KB |
Output is correct |
11 |
Correct |
90 ms |
8016 KB |
Output is correct |
12 |
Correct |
92 ms |
7876 KB |
Output is correct |
13 |
Correct |
96 ms |
8152 KB |
Output is correct |
14 |
Correct |
92 ms |
8460 KB |
Output is correct |
15 |
Correct |
100 ms |
8248 KB |
Output is correct |
16 |
Correct |
89 ms |
7964 KB |
Output is correct |
17 |
Correct |
91 ms |
8220 KB |
Output is correct |
18 |
Correct |
90 ms |
8336 KB |
Output is correct |
19 |
Correct |
88 ms |
7964 KB |
Output is correct |
20 |
Correct |
95 ms |
8332 KB |
Output is correct |
21 |
Correct |
89 ms |
8588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
6820 KB |
Output is correct |
5 |
Correct |
26 ms |
6748 KB |
Output is correct |
6 |
Correct |
26 ms |
6812 KB |
Output is correct |
7 |
Correct |
25 ms |
6236 KB |
Output is correct |
8 |
Correct |
31 ms |
6996 KB |
Output is correct |
9 |
Correct |
23 ms |
6748 KB |
Output is correct |
10 |
Correct |
28 ms |
6232 KB |
Output is correct |
11 |
Correct |
29 ms |
6744 KB |
Output is correct |
12 |
Correct |
26 ms |
6420 KB |
Output is correct |
13 |
Correct |
28 ms |
6748 KB |
Output is correct |
14 |
Correct |
29 ms |
6744 KB |
Output is correct |
15 |
Correct |
24 ms |
7000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
7952 KB |
Output is correct |
2 |
Correct |
90 ms |
8016 KB |
Output is correct |
3 |
Correct |
92 ms |
7516 KB |
Output is correct |
4 |
Correct |
92 ms |
8184 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
26 ms |
6820 KB |
Output is correct |
12 |
Correct |
26 ms |
6748 KB |
Output is correct |
13 |
Correct |
26 ms |
6812 KB |
Output is correct |
14 |
Correct |
25 ms |
6236 KB |
Output is correct |
15 |
Correct |
31 ms |
6996 KB |
Output is correct |
16 |
Correct |
23 ms |
6748 KB |
Output is correct |
17 |
Correct |
90 ms |
7992 KB |
Output is correct |
18 |
Correct |
90 ms |
8016 KB |
Output is correct |
19 |
Correct |
92 ms |
7876 KB |
Output is correct |
20 |
Correct |
96 ms |
8152 KB |
Output is correct |
21 |
Correct |
92 ms |
8460 KB |
Output is correct |
22 |
Correct |
100 ms |
8248 KB |
Output is correct |
23 |
Correct |
89 ms |
7964 KB |
Output is correct |
24 |
Correct |
91 ms |
8220 KB |
Output is correct |
25 |
Correct |
90 ms |
8336 KB |
Output is correct |
26 |
Correct |
88 ms |
7964 KB |
Output is correct |
27 |
Correct |
95 ms |
8332 KB |
Output is correct |
28 |
Correct |
89 ms |
8588 KB |
Output is correct |
29 |
Correct |
28 ms |
6232 KB |
Output is correct |
30 |
Correct |
29 ms |
6744 KB |
Output is correct |
31 |
Correct |
26 ms |
6420 KB |
Output is correct |
32 |
Correct |
28 ms |
6748 KB |
Output is correct |
33 |
Correct |
29 ms |
6744 KB |
Output is correct |
34 |
Correct |
24 ms |
7000 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
101 ms |
7696 KB |
Output is correct |
37 |
Correct |
91 ms |
8176 KB |
Output is correct |
38 |
Correct |
93 ms |
7968 KB |
Output is correct |
39 |
Correct |
92 ms |
8468 KB |
Output is correct |
40 |
Correct |
93 ms |
8500 KB |
Output is correct |
41 |
Correct |
23 ms |
6824 KB |
Output is correct |
42 |
Correct |
91 ms |
8140 KB |
Output is correct |
43 |
Correct |
94 ms |
8404 KB |
Output is correct |
44 |
Correct |
91 ms |
8456 KB |
Output is correct |
45 |
Correct |
89 ms |
8124 KB |
Output is correct |
46 |
Correct |
91 ms |
8464 KB |
Output is correct |
47 |
Correct |
92 ms |
8460 KB |
Output is correct |