#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string aa, bb;
int n = 100010;
vector< vector<int> >pref(10, vector<int>(n, 0));
void init(std::string a, std::string b) {
aa=" "+a;
bb=" "+b;
n = a.length();
/*
0 uk
1 AT
2 TA
3 AC
4 CA
5 TC
6 CT
TAC
CTA
*/
a = " " + a;
b = " " + b;
for(int i = 0; i<=6; i++)
{
pref[i][0]=0;
for(int j = 1; j<=n; j++)
{
pref[i][j]=pref[i][j-1];
if(i==0 && a[j]!=b[j])pref[i][j]++;
else if(i==1 && a[j]=='A' && b[j]=='T')pref[i][j]++;
else if(i==2 && a[j]=='T' && b[j]=='A')pref[i][j]++;
else if(i==3 && a[j]=='A' && b[j]=='C')pref[i][j]++;
else if(i==4 && a[j]=='C' && b[j]=='A')pref[i][j]++;
else if(i==5 && a[j]=='T' && b[j]=='C')pref[i][j]++;
else if(i==6 && a[j]=='C' && b[j]=='T')pref[i][j]++;
}
}
}
int get_distance(int x, int y)
{
x++;
y++;
map<char, int>m1, m2;
for(int i = x; i<=y; i++)
{
m1[aa[i]]++;
m2[bb[i]]++;
}
if(m1['A']!=m2['A'] || m1['T']!=m2['T'] || m1['C']!=m2['C'])
{
return -1;
}
int cnt = 0;
cnt += min(pref[1][y]-pref[1][x-1], pref[2][y]-pref[2][x-1]);
//cout<<cnt<<"\n";
cnt += min(pref[3][y]-pref[3][x-1], pref[4][y]-pref[4][x-1]);
//cout<<cnt<<"\n";
cnt+= min(pref[5][y]-pref[5][x-1], pref[6][y]-pref[6][x-1]);
int uk = pref[0][y]-pref[0][x-1];
int ans = cnt + 2*(uk - 2*cnt)/3;
//
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
6388 KB |
Output is correct |
2 |
Correct |
49 ms |
6612 KB |
Output is correct |
3 |
Correct |
48 ms |
6348 KB |
Output is correct |
4 |
Correct |
48 ms |
6420 KB |
Output is correct |
5 |
Correct |
2 ms |
4696 KB |
Output is correct |
6 |
Correct |
3 ms |
4700 KB |
Output is correct |
7 |
Correct |
3 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
2 ms |
4700 KB |
Output is correct |
4 |
Correct |
7 ms |
5152 KB |
Output is correct |
5 |
Correct |
7 ms |
5076 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
12 ms |
5288 KB |
Output is correct |
8 |
Correct |
12 ms |
5156 KB |
Output is correct |
9 |
Correct |
8 ms |
5064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
2 ms |
4700 KB |
Output is correct |
4 |
Correct |
7 ms |
5152 KB |
Output is correct |
5 |
Correct |
7 ms |
5076 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
12 ms |
5288 KB |
Output is correct |
8 |
Correct |
12 ms |
5156 KB |
Output is correct |
9 |
Correct |
8 ms |
5064 KB |
Output is correct |
10 |
Correct |
54 ms |
7116 KB |
Output is correct |
11 |
Correct |
56 ms |
7192 KB |
Output is correct |
12 |
Execution timed out |
1539 ms |
7096 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
2 ms |
4700 KB |
Output is correct |
3 |
Correct |
2 ms |
4700 KB |
Output is correct |
4 |
Correct |
7 ms |
5152 KB |
Output is correct |
5 |
Correct |
7 ms |
5076 KB |
Output is correct |
6 |
Correct |
7 ms |
5332 KB |
Output is correct |
7 |
Correct |
12 ms |
5288 KB |
Output is correct |
8 |
Correct |
12 ms |
5156 KB |
Output is correct |
9 |
Correct |
8 ms |
5064 KB |
Output is correct |
10 |
Correct |
8 ms |
5072 KB |
Output is correct |
11 |
Correct |
9 ms |
5328 KB |
Output is correct |
12 |
Correct |
7 ms |
5076 KB |
Output is correct |
13 |
Correct |
14 ms |
5328 KB |
Output is correct |
14 |
Correct |
21 ms |
5076 KB |
Output is correct |
15 |
Correct |
14 ms |
5584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
6388 KB |
Output is correct |
2 |
Correct |
49 ms |
6612 KB |
Output is correct |
3 |
Correct |
48 ms |
6348 KB |
Output is correct |
4 |
Correct |
48 ms |
6420 KB |
Output is correct |
5 |
Correct |
2 ms |
4696 KB |
Output is correct |
6 |
Correct |
3 ms |
4700 KB |
Output is correct |
7 |
Correct |
3 ms |
4700 KB |
Output is correct |
8 |
Correct |
2 ms |
4700 KB |
Output is correct |
9 |
Correct |
2 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
7 ms |
5152 KB |
Output is correct |
12 |
Correct |
7 ms |
5076 KB |
Output is correct |
13 |
Correct |
7 ms |
5332 KB |
Output is correct |
14 |
Correct |
12 ms |
5288 KB |
Output is correct |
15 |
Correct |
12 ms |
5156 KB |
Output is correct |
16 |
Correct |
8 ms |
5064 KB |
Output is correct |
17 |
Correct |
54 ms |
7116 KB |
Output is correct |
18 |
Correct |
56 ms |
7192 KB |
Output is correct |
19 |
Execution timed out |
1539 ms |
7096 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |