#include <iostream>
#include <cstring>
#include <map>
#include "dna.h"
#define MAX 100000
using namespace std;
int freqA1[MAX + 10], freqC1[MAX + 10], freqT1[MAX + 10], freqA2[MAX + 10], freqC2[MAX + 10], freqT2[MAX + 10], a[MAX + 10][5][5], aQuery[5][5];
map <char, int> mp;
void init(string s1, string s2)
{
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (int i = 0; i < s1.size(); i++)
{
freqA1[i + 1] = freqA1[i] + (s1[i] == 'A');
freqC1[i + 1] = freqC1[i] + (s1[i] == 'C');
freqT1[i + 1] = freqT1[i] + (s1[i] == 'T');
freqA2[i + 1] = freqA2[i] + (s2[i] == 'A');
freqC2[i + 1] = freqC2[i] + (s2[i] == 'C');
freqT2[i + 1] = freqT2[i] + (s2[i] == 'T');
if (i >= 1)
for (int ii = 0; ii <= 2; ii++)
for (int jj = 0; jj <= 2; jj++)
a[i][ii][jj] = a[i - 1][ii][jj];
a[i][mp[s1[i]]][mp[s2[i]]]++;
}
}
int get_distance(int x, int y)
{
if (freqA1[y + 1] - freqA1[x] != freqA2[y + 1] - freqA2[x])
return -1;
if (freqC1[y + 1] - freqC1[x] != freqC2[y + 1] - freqC2[x])
return -1;
if (freqT1[y + 1] - freqT1[x] != freqT2[y + 1] - freqT2[x])
return -1;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
{
aQuery[i][j] = a[y][i][j];
if (x >= 1)
aQuery[i][j] = aQuery[i][j] - a[x - 1][i][j];
}
long long ans1 = 0, ans2 = 0;
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
if (i != j)
{
int minMoves = min(aQuery[i][j], aQuery[j][i]);
ans1 = ans1 + minMoves;
aQuery[i][j] = aQuery[i][j] - minMoves;
aQuery[j][i] = aQuery[j][i] - minMoves;
ans2 = ans2 + aQuery[i][j];
}
ans2 = ans2 * 2 / 3;
return ans1 + ans2;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i < s1.size(); i++)
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
15500 KB |
Output is correct |
2 |
Correct |
50 ms |
15596 KB |
Output is correct |
3 |
Correct |
50 ms |
14428 KB |
Output is correct |
4 |
Correct |
47 ms |
15652 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
13012 KB |
Output is correct |
5 |
Correct |
9 ms |
13140 KB |
Output is correct |
6 |
Correct |
12 ms |
13128 KB |
Output is correct |
7 |
Correct |
11 ms |
12240 KB |
Output is correct |
8 |
Correct |
10 ms |
13140 KB |
Output is correct |
9 |
Correct |
9 ms |
13144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
13012 KB |
Output is correct |
5 |
Correct |
9 ms |
13140 KB |
Output is correct |
6 |
Correct |
12 ms |
13128 KB |
Output is correct |
7 |
Correct |
11 ms |
12240 KB |
Output is correct |
8 |
Correct |
10 ms |
13140 KB |
Output is correct |
9 |
Correct |
9 ms |
13144 KB |
Output is correct |
10 |
Correct |
45 ms |
15500 KB |
Output is correct |
11 |
Correct |
44 ms |
15624 KB |
Output is correct |
12 |
Correct |
47 ms |
15112 KB |
Output is correct |
13 |
Correct |
48 ms |
15380 KB |
Output is correct |
14 |
Correct |
47 ms |
15972 KB |
Output is correct |
15 |
Correct |
51 ms |
15848 KB |
Output is correct |
16 |
Correct |
45 ms |
15032 KB |
Output is correct |
17 |
Correct |
44 ms |
15352 KB |
Output is correct |
18 |
Correct |
48 ms |
15848 KB |
Output is correct |
19 |
Correct |
35 ms |
15000 KB |
Output is correct |
20 |
Correct |
53 ms |
15292 KB |
Output is correct |
21 |
Correct |
35 ms |
15868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
13012 KB |
Output is correct |
5 |
Correct |
9 ms |
13140 KB |
Output is correct |
6 |
Correct |
12 ms |
13128 KB |
Output is correct |
7 |
Correct |
11 ms |
12240 KB |
Output is correct |
8 |
Correct |
10 ms |
13140 KB |
Output is correct |
9 |
Correct |
9 ms |
13144 KB |
Output is correct |
10 |
Correct |
8 ms |
12060 KB |
Output is correct |
11 |
Correct |
10 ms |
13136 KB |
Output is correct |
12 |
Correct |
8 ms |
12372 KB |
Output is correct |
13 |
Correct |
10 ms |
13112 KB |
Output is correct |
14 |
Correct |
10 ms |
13140 KB |
Output is correct |
15 |
Correct |
10 ms |
13140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
15500 KB |
Output is correct |
2 |
Correct |
50 ms |
15596 KB |
Output is correct |
3 |
Correct |
50 ms |
14428 KB |
Output is correct |
4 |
Correct |
47 ms |
15652 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
8 ms |
13012 KB |
Output is correct |
12 |
Correct |
9 ms |
13140 KB |
Output is correct |
13 |
Correct |
12 ms |
13128 KB |
Output is correct |
14 |
Correct |
11 ms |
12240 KB |
Output is correct |
15 |
Correct |
10 ms |
13140 KB |
Output is correct |
16 |
Correct |
9 ms |
13144 KB |
Output is correct |
17 |
Correct |
45 ms |
15500 KB |
Output is correct |
18 |
Correct |
44 ms |
15624 KB |
Output is correct |
19 |
Correct |
47 ms |
15112 KB |
Output is correct |
20 |
Correct |
48 ms |
15380 KB |
Output is correct |
21 |
Correct |
47 ms |
15972 KB |
Output is correct |
22 |
Correct |
51 ms |
15848 KB |
Output is correct |
23 |
Correct |
45 ms |
15032 KB |
Output is correct |
24 |
Correct |
44 ms |
15352 KB |
Output is correct |
25 |
Correct |
48 ms |
15848 KB |
Output is correct |
26 |
Correct |
35 ms |
15000 KB |
Output is correct |
27 |
Correct |
53 ms |
15292 KB |
Output is correct |
28 |
Correct |
35 ms |
15868 KB |
Output is correct |
29 |
Correct |
8 ms |
12060 KB |
Output is correct |
30 |
Correct |
10 ms |
13136 KB |
Output is correct |
31 |
Correct |
8 ms |
12372 KB |
Output is correct |
32 |
Correct |
10 ms |
13112 KB |
Output is correct |
33 |
Correct |
10 ms |
13140 KB |
Output is correct |
34 |
Correct |
10 ms |
13140 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
50 ms |
14440 KB |
Output is correct |
37 |
Correct |
45 ms |
15568 KB |
Output is correct |
38 |
Correct |
48 ms |
15240 KB |
Output is correct |
39 |
Correct |
45 ms |
15988 KB |
Output is correct |
40 |
Correct |
48 ms |
15980 KB |
Output is correct |
41 |
Correct |
9 ms |
13156 KB |
Output is correct |
42 |
Correct |
46 ms |
15196 KB |
Output is correct |
43 |
Correct |
45 ms |
15880 KB |
Output is correct |
44 |
Correct |
41 ms |
15852 KB |
Output is correct |
45 |
Correct |
37 ms |
15212 KB |
Output is correct |
46 |
Correct |
34 ms |
16008 KB |
Output is correct |
47 |
Correct |
35 ms |
15892 KB |
Output is correct |