#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 69;
int a[N][3];
int b[N][3];
int p[N][3][3];
int n;
void init(string A, string B) {
n = A.length();
for (int i = 1; i <= n; i++){
if (A[i - 1] == 'A') a[i][0]++;
else if (A[i - 1] == 'T') a[i][1]++;
else a[i][2]++;
}
for (int i = 1; i <= n; i++){
if (B[i - 1] == 'A') b[i][0]++;
else if (B[i - 1] == 'T') b[i][1]++;
else b[i][2]++;
}
for (int i = 1; i <= n; i++){
int k1 = 0, k2 = 0;
for (int j = 0; j < 3; j++){
if (a[i][j] > 0) k1 = j;
if (b[i][j] > 0) k2 = j;
}
p[i][k1][k2]++;
}
for (int i = 1; i <= n; i++){
for (int j = 0; j < 3; j++){
a[i][j] += a[i - 1][j];
b[i][j] += b[i - 1][j];
for (int k = 0; k < 3; k++)
p[i][j][k] += p[i - 1][j][k];
}
}
}
int get_distance(int x, int y) {
x++;
y++;
int ans = 0;
for (int j = 0; j < 3; j++){
int v1 = a[y][j] - a[x - 1][j];
int v2 = b[y][j] - b[x - 1][j];
if (v1 != v2) return -1;
}
int change[3][3];
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
if (j != k)
change[j][k] = p[y][j][k] - p[x - 1][j][k];
else change[j][k] = 0;
}
}
for (int j = 0; j < 3; j++){
for (int k = j + 1; k < 3; k++){
int op = min(change[j][k], change[k][j]);
ans += op;
change[j][k] -= op;
change[k][j] -= op;
ans += change[j][k] + change[k][j];
}
}
int mx = -1;
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
mx = max(mx, change[j][k]);
}
}
ans -= mx;
return ans;
}
// int32_t main(){
// string a, b; cin >> a >> b;
// init(a, b);
// int q; cin >> q;
// while(q--){
// int x, y; cin >> x >> y;
// cout << get_distance(x, y) << "\n";
// }
// return 0;
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
7944 KB |
Output is correct |
2 |
Correct |
38 ms |
8068 KB |
Output is correct |
3 |
Correct |
40 ms |
7452 KB |
Output is correct |
4 |
Correct |
34 ms |
8016 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
6612 KB |
Output is correct |
5 |
Correct |
7 ms |
6740 KB |
Output is correct |
6 |
Correct |
6 ms |
6612 KB |
Output is correct |
7 |
Correct |
7 ms |
6228 KB |
Output is correct |
8 |
Correct |
6 ms |
6696 KB |
Output is correct |
9 |
Correct |
6 ms |
6740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
6612 KB |
Output is correct |
5 |
Correct |
7 ms |
6740 KB |
Output is correct |
6 |
Correct |
6 ms |
6612 KB |
Output is correct |
7 |
Correct |
7 ms |
6228 KB |
Output is correct |
8 |
Correct |
6 ms |
6696 KB |
Output is correct |
9 |
Correct |
6 ms |
6740 KB |
Output is correct |
10 |
Correct |
38 ms |
7912 KB |
Output is correct |
11 |
Correct |
38 ms |
8068 KB |
Output is correct |
12 |
Correct |
39 ms |
7972 KB |
Output is correct |
13 |
Correct |
37 ms |
8124 KB |
Output is correct |
14 |
Correct |
36 ms |
8324 KB |
Output is correct |
15 |
Correct |
35 ms |
8332 KB |
Output is correct |
16 |
Correct |
35 ms |
7912 KB |
Output is correct |
17 |
Correct |
33 ms |
8084 KB |
Output is correct |
18 |
Correct |
35 ms |
8352 KB |
Output is correct |
19 |
Correct |
31 ms |
7928 KB |
Output is correct |
20 |
Correct |
42 ms |
8196 KB |
Output is correct |
21 |
Correct |
49 ms |
8412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
6612 KB |
Output is correct |
5 |
Correct |
7 ms |
6740 KB |
Output is correct |
6 |
Correct |
6 ms |
6612 KB |
Output is correct |
7 |
Correct |
7 ms |
6228 KB |
Output is correct |
8 |
Correct |
6 ms |
6696 KB |
Output is correct |
9 |
Correct |
6 ms |
6740 KB |
Output is correct |
10 |
Correct |
5 ms |
6100 KB |
Output is correct |
11 |
Correct |
7 ms |
6740 KB |
Output is correct |
12 |
Correct |
5 ms |
6304 KB |
Output is correct |
13 |
Correct |
6 ms |
6612 KB |
Output is correct |
14 |
Correct |
6 ms |
6740 KB |
Output is correct |
15 |
Correct |
7 ms |
6776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
7944 KB |
Output is correct |
2 |
Correct |
38 ms |
8068 KB |
Output is correct |
3 |
Correct |
40 ms |
7452 KB |
Output is correct |
4 |
Correct |
34 ms |
8016 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
7 ms |
6612 KB |
Output is correct |
12 |
Correct |
7 ms |
6740 KB |
Output is correct |
13 |
Correct |
6 ms |
6612 KB |
Output is correct |
14 |
Correct |
7 ms |
6228 KB |
Output is correct |
15 |
Correct |
6 ms |
6696 KB |
Output is correct |
16 |
Correct |
6 ms |
6740 KB |
Output is correct |
17 |
Correct |
38 ms |
7912 KB |
Output is correct |
18 |
Correct |
38 ms |
8068 KB |
Output is correct |
19 |
Correct |
39 ms |
7972 KB |
Output is correct |
20 |
Correct |
37 ms |
8124 KB |
Output is correct |
21 |
Correct |
36 ms |
8324 KB |
Output is correct |
22 |
Correct |
35 ms |
8332 KB |
Output is correct |
23 |
Correct |
35 ms |
7912 KB |
Output is correct |
24 |
Correct |
33 ms |
8084 KB |
Output is correct |
25 |
Correct |
35 ms |
8352 KB |
Output is correct |
26 |
Correct |
31 ms |
7928 KB |
Output is correct |
27 |
Correct |
42 ms |
8196 KB |
Output is correct |
28 |
Correct |
49 ms |
8412 KB |
Output is correct |
29 |
Correct |
5 ms |
6100 KB |
Output is correct |
30 |
Correct |
7 ms |
6740 KB |
Output is correct |
31 |
Correct |
5 ms |
6304 KB |
Output is correct |
32 |
Correct |
6 ms |
6612 KB |
Output is correct |
33 |
Correct |
6 ms |
6740 KB |
Output is correct |
34 |
Correct |
7 ms |
6776 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
34 ms |
7476 KB |
Output is correct |
37 |
Correct |
39 ms |
8024 KB |
Output is correct |
38 |
Correct |
39 ms |
8060 KB |
Output is correct |
39 |
Correct |
42 ms |
8468 KB |
Output is correct |
40 |
Correct |
36 ms |
8384 KB |
Output is correct |
41 |
Correct |
5 ms |
6740 KB |
Output is correct |
42 |
Correct |
33 ms |
8060 KB |
Output is correct |
43 |
Correct |
33 ms |
8408 KB |
Output is correct |
44 |
Correct |
31 ms |
8336 KB |
Output is correct |
45 |
Correct |
30 ms |
8080 KB |
Output is correct |
46 |
Correct |
33 ms |
8456 KB |
Output is correct |
47 |
Correct |
38 ms |
8396 KB |
Output is correct |