#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
int letters[100005][3][3];
pair< pair<int, int>, int> changes[6] = {{{0, 1}, 2}, {{0, 2}, 1}, {{1, 0}, 2}, {{1, 2}, 0}, {{2, 0}, 1}, {{2, 1}, 0}};
void init(string a, string b) {
int n = a.size();
for(int i = 0; i < n; i++)
{
if(i > 0)
{
for(int l = 0; l < 3; l++)
for(int k = 0; k < 3; k++)
letters[i][l][k] = letters[i - 1][l][k];
}
if(a[i] == 'T')
a[i] = 'B';
if(b[i] == 'T')
b[i] = 'B';
letters[i][a[i] - 'A'][b[i] - 'A']++;
//cout << i << "\n";
}
}
int get_distance(int x, int y) {
int temp[3][3];
for(int i = 0; i < 3; i++) {
for(int l = 0; l < 3; l++) {
temp[i][l] = letters[y][i][l];
}
}
if(x != 0)
{
for(int i = 0; i < 3; i++) {
for(int l = 0; l < 3; l++) {
temp[i][l] -= letters[x - 1][i][l];
}
}
}
long long res = 0;
for(int i = 0; i < 3; i++)
{
for(int l = 0; l < 3; l++)
{
if(i == l)
continue;
long long val = min(temp[i][l], temp[l][i]);
res += val;
temp[i][l] -= val;
temp[l][i] -= val;
temp[i][i] += val;
temp[l][l] += val;
}
}
//cout << temp[0][0] << " " << temp[1][1] << " " << temp[2][2]<< "\n";
for(int i = 0; i < 3; i++)
{
for(int l = 0; l < 3; l++)
{
if(i == l)
continue;
int oth = 3 - i - l;
long long val = min(temp[i][oth], temp[l][i]);
res += val;
temp[i][oth] -= val;
temp[l][i] -= val;
temp[i][i] += val;
temp[l][oth] += val;
val = min(temp[l][oth], temp[oth][l]);
res += val;
temp[oth][l] -= val;
temp[l][oth] -= val;
temp[oth][oth] += val;
temp[l][l] += val;
}
}
int curr = temp[0][0] + temp[1][1] + temp[2][2];
//cout << curr << " " << temp[0][0] << " " << temp[1][1] << " " << temp[2][2]<< "\n";
if(curr != y - x + 1)
res = -1;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
6968 KB |
Output is correct |
2 |
Correct |
37 ms |
6980 KB |
Output is correct |
3 |
Correct |
37 ms |
6560 KB |
Output is correct |
4 |
Correct |
39 ms |
7020 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 |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
4436 KB |
Output is correct |
5 |
Correct |
5 ms |
4540 KB |
Output is correct |
6 |
Correct |
4 ms |
4548 KB |
Output is correct |
7 |
Correct |
5 ms |
4304 KB |
Output is correct |
8 |
Correct |
5 ms |
4548 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
4436 KB |
Output is correct |
5 |
Correct |
5 ms |
4540 KB |
Output is correct |
6 |
Correct |
4 ms |
4548 KB |
Output is correct |
7 |
Correct |
5 ms |
4304 KB |
Output is correct |
8 |
Correct |
5 ms |
4548 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
38 ms |
6884 KB |
Output is correct |
11 |
Correct |
37 ms |
7048 KB |
Output is correct |
12 |
Correct |
37 ms |
7072 KB |
Output is correct |
13 |
Correct |
37 ms |
7144 KB |
Output is correct |
14 |
Correct |
39 ms |
7408 KB |
Output is correct |
15 |
Correct |
41 ms |
7236 KB |
Output is correct |
16 |
Correct |
36 ms |
6984 KB |
Output is correct |
17 |
Correct |
36 ms |
7060 KB |
Output is correct |
18 |
Correct |
37 ms |
7284 KB |
Output is correct |
19 |
Correct |
34 ms |
6960 KB |
Output is correct |
20 |
Correct |
34 ms |
7160 KB |
Output is correct |
21 |
Correct |
35 ms |
7264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
4436 KB |
Output is correct |
5 |
Correct |
5 ms |
4540 KB |
Output is correct |
6 |
Correct |
4 ms |
4548 KB |
Output is correct |
7 |
Correct |
5 ms |
4304 KB |
Output is correct |
8 |
Correct |
5 ms |
4548 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
4 ms |
4160 KB |
Output is correct |
11 |
Correct |
4 ms |
4564 KB |
Output is correct |
12 |
Correct |
4 ms |
4312 KB |
Output is correct |
13 |
Correct |
4 ms |
4564 KB |
Output is correct |
14 |
Correct |
4 ms |
4544 KB |
Output is correct |
15 |
Correct |
4 ms |
4544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
6968 KB |
Output is correct |
2 |
Correct |
37 ms |
6980 KB |
Output is correct |
3 |
Correct |
37 ms |
6560 KB |
Output is correct |
4 |
Correct |
39 ms |
7020 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 |
308 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
4 ms |
4436 KB |
Output is correct |
12 |
Correct |
5 ms |
4540 KB |
Output is correct |
13 |
Correct |
4 ms |
4548 KB |
Output is correct |
14 |
Correct |
5 ms |
4304 KB |
Output is correct |
15 |
Correct |
5 ms |
4548 KB |
Output is correct |
16 |
Correct |
4 ms |
4564 KB |
Output is correct |
17 |
Correct |
38 ms |
6884 KB |
Output is correct |
18 |
Correct |
37 ms |
7048 KB |
Output is correct |
19 |
Correct |
37 ms |
7072 KB |
Output is correct |
20 |
Correct |
37 ms |
7144 KB |
Output is correct |
21 |
Correct |
39 ms |
7408 KB |
Output is correct |
22 |
Correct |
41 ms |
7236 KB |
Output is correct |
23 |
Correct |
36 ms |
6984 KB |
Output is correct |
24 |
Correct |
36 ms |
7060 KB |
Output is correct |
25 |
Correct |
37 ms |
7284 KB |
Output is correct |
26 |
Correct |
34 ms |
6960 KB |
Output is correct |
27 |
Correct |
34 ms |
7160 KB |
Output is correct |
28 |
Correct |
35 ms |
7264 KB |
Output is correct |
29 |
Correct |
4 ms |
4160 KB |
Output is correct |
30 |
Correct |
4 ms |
4564 KB |
Output is correct |
31 |
Correct |
4 ms |
4312 KB |
Output is correct |
32 |
Correct |
4 ms |
4564 KB |
Output is correct |
33 |
Correct |
4 ms |
4544 KB |
Output is correct |
34 |
Correct |
4 ms |
4544 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
37 ms |
6604 KB |
Output is correct |
37 |
Correct |
38 ms |
7056 KB |
Output is correct |
38 |
Correct |
46 ms |
7168 KB |
Output is correct |
39 |
Correct |
38 ms |
7364 KB |
Output is correct |
40 |
Correct |
36 ms |
7396 KB |
Output is correct |
41 |
Correct |
4 ms |
4564 KB |
Output is correct |
42 |
Correct |
34 ms |
7060 KB |
Output is correct |
43 |
Correct |
35 ms |
7292 KB |
Output is correct |
44 |
Correct |
35 ms |
7256 KB |
Output is correct |
45 |
Correct |
35 ms |
7016 KB |
Output is correct |
46 |
Correct |
35 ms |
7288 KB |
Output is correct |
47 |
Correct |
34 ms |
7260 KB |
Output is correct |