#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5 + 5;
int dp[MAX][3][3];
int n;
void init(string a, string b){
map<char, char> m = {{'A', 0}, {'T', 1}, {'C', 2}};
n = a.size();
for (int i = 0; i < n; i++)
{
a[i] = m[a[i]];
b[i] = m[b[i]];
}
if(a[0] != b[0]) dp[0][a[0]][b[0]]++;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
dp[i][j][k] = dp[i - 1][j][k];
if(a[i] != b[i]) dp[i][a[i]][b[i]]++;
}
}
int get_distance(int x, int y){
int c[3][3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
c[i][j] = dp[y][i][j];
if(x != 0) c[i][j] -= dp[x - 1][i][j];
}
}
int ans = 0;
ans = min(c[0][1], c[1][0]) + min(c[1][2], c[2][1]) + min(c[0][2], c[2][0]);
if((c[0][1] - c[1][0]) == (c[2][0] - c[0][2]) && (c[2][0] - c[0][2]) == (c[1][2] - c[2][1])) return (ans + 2 * abs(c[0][1] - c[1][0]));
return -1;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:16:32: warning: array subscript has type 'char' [-Wchar-subscripts]
16 | if(a[0] != b[0]) dp[0][a[0]][b[0]]++;
| ^
dna.cpp:16:38: warning: array subscript has type 'char' [-Wchar-subscripts]
16 | if(a[0] != b[0]) dp[0][a[0]][b[0]]++;
| ^
dna.cpp:22:36: warning: array subscript has type 'char' [-Wchar-subscripts]
22 | if(a[i] != b[i]) dp[i][a[i]][b[i]]++;
| ^
dna.cpp:22:42: warning: array subscript has type 'char' [-Wchar-subscripts]
22 | if(a[i] != b[i]) dp[i][a[i]][b[i]]++;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
7032 KB |
Output is correct |
2 |
Correct |
33 ms |
5956 KB |
Output is correct |
3 |
Correct |
41 ms |
5532 KB |
Output is correct |
4 |
Correct |
33 ms |
5856 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4548 KB |
Output is correct |
5 |
Correct |
6 ms |
4564 KB |
Output is correct |
6 |
Correct |
6 ms |
4564 KB |
Output is correct |
7 |
Correct |
5 ms |
4308 KB |
Output is correct |
8 |
Correct |
5 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4548 KB |
Output is correct |
5 |
Correct |
6 ms |
4564 KB |
Output is correct |
6 |
Correct |
6 ms |
4564 KB |
Output is correct |
7 |
Correct |
5 ms |
4308 KB |
Output is correct |
8 |
Correct |
5 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4548 KB |
Output is correct |
10 |
Correct |
36 ms |
5804 KB |
Output is correct |
11 |
Correct |
35 ms |
5896 KB |
Output is correct |
12 |
Correct |
34 ms |
5996 KB |
Output is correct |
13 |
Correct |
33 ms |
6080 KB |
Output is correct |
14 |
Correct |
42 ms |
6308 KB |
Output is correct |
15 |
Correct |
32 ms |
6156 KB |
Output is correct |
16 |
Correct |
32 ms |
5960 KB |
Output is correct |
17 |
Correct |
33 ms |
6164 KB |
Output is correct |
18 |
Correct |
33 ms |
6212 KB |
Output is correct |
19 |
Correct |
35 ms |
5968 KB |
Output is correct |
20 |
Correct |
31 ms |
6256 KB |
Output is correct |
21 |
Correct |
31 ms |
6452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
4548 KB |
Output is correct |
5 |
Correct |
6 ms |
4564 KB |
Output is correct |
6 |
Correct |
6 ms |
4564 KB |
Output is correct |
7 |
Correct |
5 ms |
4308 KB |
Output is correct |
8 |
Correct |
5 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4548 KB |
Output is correct |
10 |
Correct |
6 ms |
4180 KB |
Output is correct |
11 |
Correct |
6 ms |
4580 KB |
Output is correct |
12 |
Correct |
5 ms |
4264 KB |
Output is correct |
13 |
Correct |
6 ms |
4576 KB |
Output is correct |
14 |
Correct |
6 ms |
4544 KB |
Output is correct |
15 |
Correct |
5 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
7032 KB |
Output is correct |
2 |
Correct |
33 ms |
5956 KB |
Output is correct |
3 |
Correct |
41 ms |
5532 KB |
Output is correct |
4 |
Correct |
33 ms |
5856 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
6 ms |
4548 KB |
Output is correct |
12 |
Correct |
6 ms |
4564 KB |
Output is correct |
13 |
Correct |
6 ms |
4564 KB |
Output is correct |
14 |
Correct |
5 ms |
4308 KB |
Output is correct |
15 |
Correct |
5 ms |
4564 KB |
Output is correct |
16 |
Correct |
4 ms |
4548 KB |
Output is correct |
17 |
Correct |
36 ms |
5804 KB |
Output is correct |
18 |
Correct |
35 ms |
5896 KB |
Output is correct |
19 |
Correct |
34 ms |
5996 KB |
Output is correct |
20 |
Correct |
33 ms |
6080 KB |
Output is correct |
21 |
Correct |
42 ms |
6308 KB |
Output is correct |
22 |
Correct |
32 ms |
6156 KB |
Output is correct |
23 |
Correct |
32 ms |
5960 KB |
Output is correct |
24 |
Correct |
33 ms |
6164 KB |
Output is correct |
25 |
Correct |
33 ms |
6212 KB |
Output is correct |
26 |
Correct |
35 ms |
5968 KB |
Output is correct |
27 |
Correct |
31 ms |
6256 KB |
Output is correct |
28 |
Correct |
31 ms |
6452 KB |
Output is correct |
29 |
Correct |
6 ms |
4180 KB |
Output is correct |
30 |
Correct |
6 ms |
4580 KB |
Output is correct |
31 |
Correct |
5 ms |
4264 KB |
Output is correct |
32 |
Correct |
6 ms |
4576 KB |
Output is correct |
33 |
Correct |
6 ms |
4544 KB |
Output is correct |
34 |
Correct |
5 ms |
4564 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
37 ms |
5544 KB |
Output is correct |
37 |
Correct |
36 ms |
5900 KB |
Output is correct |
38 |
Correct |
36 ms |
6048 KB |
Output is correct |
39 |
Correct |
35 ms |
6312 KB |
Output is correct |
40 |
Correct |
38 ms |
6368 KB |
Output is correct |
41 |
Correct |
4 ms |
4564 KB |
Output is correct |
42 |
Correct |
39 ms |
5992 KB |
Output is correct |
43 |
Correct |
31 ms |
6236 KB |
Output is correct |
44 |
Correct |
31 ms |
6264 KB |
Output is correct |
45 |
Correct |
31 ms |
6124 KB |
Output is correct |
46 |
Correct |
32 ms |
6344 KB |
Output is correct |
47 |
Correct |
30 ms |
6268 KB |
Output is correct |