#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int L = 3;
int vA[N][L], vB[N][L];
int p[N][L][L];
map <char, int> mp;
void init(string a, string b)
{
int n = a.size(), i, j, h;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (i = 1; i <= n; i++)
{
for (j = 0; j < L; j++)
{
vA[i][j] = vA[i - 1][j];
vB[i][j] = vB[i - 1][j];
}
for (j = 0; j < L; j++)
for (h = 0; h < L; h++)
p[i][j][h] = p[i - 1][j][h];
int f = mp[a[i - 1]], s = mp[b[i - 1]];
vA[i][f]++;
vB[i][s]++;
p[i][f][s]++;
}
}
int get_distance(int x, int y)
{
int i, j, h, cnt = 0, maxi = 0;
y++;
for (i = 0; i < L; i++)
if (vA[y][i] - vA[x][i] != vB[y][i] - vB[x][i])
return -1;
for (i = 0; i < L; i++)
for (j = i + 1; j < L; j++)
{
int a = p[y][i][j] - p[x][i][j];
int b = p[y][j][i] - p[x][j][i];
cnt += min(a, b);
maxi = max(maxi, max(a, b) - min(a, b));
}
return cnt + 2 * maxi;
}/*
int main()
{
int n, q;
assert(scanf("%d %d", &n, &q) == 2);
char A[n+1], B[n+1];
assert(scanf("%s", A) == 1);
assert(scanf("%s", B) == 1);
std::string a = std::string(A);
std::string b = std::string(B);
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d %d", &x[i], &y[i]) == 2);
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", results[i]);
}
fclose(stdout);
return 0;
}*/
Compilation message
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:33:15: warning: unused variable 'h' [-Wunused-variable]
33 | int i, j, h, cnt = 0, maxi = 0;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
9220 KB |
Output is correct |
2 |
Correct |
45 ms |
9344 KB |
Output is correct |
3 |
Correct |
46 ms |
8704 KB |
Output is correct |
4 |
Correct |
46 ms |
9344 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
7 ms |
6848 KB |
Output is correct |
5 |
Correct |
7 ms |
6860 KB |
Output is correct |
6 |
Correct |
7 ms |
6860 KB |
Output is correct |
7 |
Correct |
7 ms |
6476 KB |
Output is correct |
8 |
Correct |
7 ms |
6860 KB |
Output is correct |
9 |
Correct |
6 ms |
6836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
7 ms |
6848 KB |
Output is correct |
5 |
Correct |
7 ms |
6860 KB |
Output is correct |
6 |
Correct |
7 ms |
6860 KB |
Output is correct |
7 |
Correct |
7 ms |
6476 KB |
Output is correct |
8 |
Correct |
7 ms |
6860 KB |
Output is correct |
9 |
Correct |
6 ms |
6836 KB |
Output is correct |
10 |
Correct |
46 ms |
9284 KB |
Output is correct |
11 |
Correct |
44 ms |
9344 KB |
Output is correct |
12 |
Correct |
46 ms |
9184 KB |
Output is correct |
13 |
Correct |
57 ms |
9384 KB |
Output is correct |
14 |
Correct |
47 ms |
9712 KB |
Output is correct |
15 |
Correct |
46 ms |
9616 KB |
Output is correct |
16 |
Correct |
41 ms |
9188 KB |
Output is correct |
17 |
Correct |
42 ms |
9356 KB |
Output is correct |
18 |
Correct |
41 ms |
9560 KB |
Output is correct |
19 |
Correct |
41 ms |
9216 KB |
Output is correct |
20 |
Correct |
38 ms |
9324 KB |
Output is correct |
21 |
Correct |
39 ms |
9600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
7 ms |
6848 KB |
Output is correct |
5 |
Correct |
7 ms |
6860 KB |
Output is correct |
6 |
Correct |
7 ms |
6860 KB |
Output is correct |
7 |
Correct |
7 ms |
6476 KB |
Output is correct |
8 |
Correct |
7 ms |
6860 KB |
Output is correct |
9 |
Correct |
6 ms |
6836 KB |
Output is correct |
10 |
Correct |
6 ms |
6348 KB |
Output is correct |
11 |
Correct |
7 ms |
6860 KB |
Output is correct |
12 |
Correct |
7 ms |
6432 KB |
Output is correct |
13 |
Correct |
7 ms |
6840 KB |
Output is correct |
14 |
Correct |
7 ms |
6860 KB |
Output is correct |
15 |
Correct |
6 ms |
6860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
9220 KB |
Output is correct |
2 |
Correct |
45 ms |
9344 KB |
Output is correct |
3 |
Correct |
46 ms |
8704 KB |
Output is correct |
4 |
Correct |
46 ms |
9344 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
7 ms |
6848 KB |
Output is correct |
12 |
Correct |
7 ms |
6860 KB |
Output is correct |
13 |
Correct |
7 ms |
6860 KB |
Output is correct |
14 |
Correct |
7 ms |
6476 KB |
Output is correct |
15 |
Correct |
7 ms |
6860 KB |
Output is correct |
16 |
Correct |
6 ms |
6836 KB |
Output is correct |
17 |
Correct |
46 ms |
9284 KB |
Output is correct |
18 |
Correct |
44 ms |
9344 KB |
Output is correct |
19 |
Correct |
46 ms |
9184 KB |
Output is correct |
20 |
Correct |
57 ms |
9384 KB |
Output is correct |
21 |
Correct |
47 ms |
9712 KB |
Output is correct |
22 |
Correct |
46 ms |
9616 KB |
Output is correct |
23 |
Correct |
41 ms |
9188 KB |
Output is correct |
24 |
Correct |
42 ms |
9356 KB |
Output is correct |
25 |
Correct |
41 ms |
9560 KB |
Output is correct |
26 |
Correct |
41 ms |
9216 KB |
Output is correct |
27 |
Correct |
38 ms |
9324 KB |
Output is correct |
28 |
Correct |
39 ms |
9600 KB |
Output is correct |
29 |
Correct |
6 ms |
6348 KB |
Output is correct |
30 |
Correct |
7 ms |
6860 KB |
Output is correct |
31 |
Correct |
7 ms |
6432 KB |
Output is correct |
32 |
Correct |
7 ms |
6840 KB |
Output is correct |
33 |
Correct |
7 ms |
6860 KB |
Output is correct |
34 |
Correct |
6 ms |
6860 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
46 ms |
8792 KB |
Output is correct |
37 |
Correct |
45 ms |
9288 KB |
Output is correct |
38 |
Correct |
44 ms |
9356 KB |
Output is correct |
39 |
Correct |
49 ms |
9716 KB |
Output is correct |
40 |
Correct |
45 ms |
9708 KB |
Output is correct |
41 |
Correct |
6 ms |
6860 KB |
Output is correct |
42 |
Correct |
42 ms |
9220 KB |
Output is correct |
43 |
Correct |
44 ms |
9588 KB |
Output is correct |
44 |
Correct |
46 ms |
9644 KB |
Output is correct |
45 |
Correct |
40 ms |
9224 KB |
Output is correct |
46 |
Correct |
40 ms |
9580 KB |
Output is correct |
47 |
Correct |
46 ms |
9600 KB |
Output is correct |