# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
476803 |
2021-09-28T14:27:32 Z |
Drew_ |
Mutating DNA (IOI21_dna) |
C++17 |
|
50 ms |
9716 KB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e5 + 69;
int n;
int fqa[MAX][3] = {}, fqb[MAX][3] = {};
int tf[MAX][3][3] = {};
void init(string a, string b) {
n = (int) a.size();
const auto get = [](char c) -> int
{
if (c == 'A')
return 0;
if (c == 'T')
return 1;
return 2;
};
for (int i = 1; i <= n; ++i)
{
int x = get(a[i-1]), y = get(b[i-1]);
fqa[i][x] = 1; fqb[i][y] = 1;
tf[i][x][y] = 1;
}
for (int j = 0; j < 3; ++j)
for (int i = 1; i <= n; ++i)
fqa[i][j] += fqa[i-1][j], fqb[i][j] += fqb[i-1][j];
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
for (int i = 1; i <= n; ++i)
tf[i][j][k] += tf[i-1][j][k];
}
int get_distance(int l, int r) {
l++, r++;
for (int i = 0; i < 3; ++i)
if (fqa[r][i] - fqa[l-1][i] != fqb[r][i] - fqb[l-1][i])
return -1;
int res = r-l+1, ctr = 0;
for (int i = 0; i < 3; ++i)
res -= (tf[r][i][i] - tf[l-1][i][i]);
for (int i = 0; i < 3; ++i)
for (int j = i+1; j < 3; ++j)
{
ctr += min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
res -= 2 * min(tf[r][i][j] - tf[l-1][i][j], tf[r][j][i] - tf[l-1][j][i]);
}
assert(res % 3 == 0);
return ctr + 2*res/3;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
9220 KB |
Output is correct |
2 |
Correct |
44 ms |
9344 KB |
Output is correct |
3 |
Correct |
43 ms |
8792 KB |
Output is correct |
4 |
Correct |
42 ms |
9324 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
6876 KB |
Output is correct |
5 |
Correct |
9 ms |
6956 KB |
Output is correct |
6 |
Correct |
9 ms |
6860 KB |
Output is correct |
7 |
Correct |
8 ms |
6476 KB |
Output is correct |
8 |
Correct |
9 ms |
6860 KB |
Output is correct |
9 |
Correct |
8 ms |
6840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
6876 KB |
Output is correct |
5 |
Correct |
9 ms |
6956 KB |
Output is correct |
6 |
Correct |
9 ms |
6860 KB |
Output is correct |
7 |
Correct |
8 ms |
6476 KB |
Output is correct |
8 |
Correct |
9 ms |
6860 KB |
Output is correct |
9 |
Correct |
8 ms |
6840 KB |
Output is correct |
10 |
Correct |
44 ms |
9328 KB |
Output is correct |
11 |
Correct |
48 ms |
9344 KB |
Output is correct |
12 |
Correct |
50 ms |
9204 KB |
Output is correct |
13 |
Correct |
44 ms |
9396 KB |
Output is correct |
14 |
Correct |
50 ms |
9716 KB |
Output is correct |
15 |
Correct |
48 ms |
9600 KB |
Output is correct |
16 |
Correct |
43 ms |
9176 KB |
Output is correct |
17 |
Correct |
40 ms |
9352 KB |
Output is correct |
18 |
Correct |
45 ms |
9576 KB |
Output is correct |
19 |
Correct |
39 ms |
9196 KB |
Output is correct |
20 |
Correct |
38 ms |
9388 KB |
Output is correct |
21 |
Correct |
39 ms |
9600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
6876 KB |
Output is correct |
5 |
Correct |
9 ms |
6956 KB |
Output is correct |
6 |
Correct |
9 ms |
6860 KB |
Output is correct |
7 |
Correct |
8 ms |
6476 KB |
Output is correct |
8 |
Correct |
9 ms |
6860 KB |
Output is correct |
9 |
Correct |
8 ms |
6840 KB |
Output is correct |
10 |
Correct |
8 ms |
6344 KB |
Output is correct |
11 |
Correct |
9 ms |
6860 KB |
Output is correct |
12 |
Correct |
8 ms |
6476 KB |
Output is correct |
13 |
Correct |
9 ms |
6840 KB |
Output is correct |
14 |
Correct |
9 ms |
6860 KB |
Output is correct |
15 |
Correct |
8 ms |
6860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
9220 KB |
Output is correct |
2 |
Correct |
44 ms |
9344 KB |
Output is correct |
3 |
Correct |
43 ms |
8792 KB |
Output is correct |
4 |
Correct |
42 ms |
9324 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
9 ms |
6876 KB |
Output is correct |
12 |
Correct |
9 ms |
6956 KB |
Output is correct |
13 |
Correct |
9 ms |
6860 KB |
Output is correct |
14 |
Correct |
8 ms |
6476 KB |
Output is correct |
15 |
Correct |
9 ms |
6860 KB |
Output is correct |
16 |
Correct |
8 ms |
6840 KB |
Output is correct |
17 |
Correct |
44 ms |
9328 KB |
Output is correct |
18 |
Correct |
48 ms |
9344 KB |
Output is correct |
19 |
Correct |
50 ms |
9204 KB |
Output is correct |
20 |
Correct |
44 ms |
9396 KB |
Output is correct |
21 |
Correct |
50 ms |
9716 KB |
Output is correct |
22 |
Correct |
48 ms |
9600 KB |
Output is correct |
23 |
Correct |
43 ms |
9176 KB |
Output is correct |
24 |
Correct |
40 ms |
9352 KB |
Output is correct |
25 |
Correct |
45 ms |
9576 KB |
Output is correct |
26 |
Correct |
39 ms |
9196 KB |
Output is correct |
27 |
Correct |
38 ms |
9388 KB |
Output is correct |
28 |
Correct |
39 ms |
9600 KB |
Output is correct |
29 |
Correct |
8 ms |
6344 KB |
Output is correct |
30 |
Correct |
9 ms |
6860 KB |
Output is correct |
31 |
Correct |
8 ms |
6476 KB |
Output is correct |
32 |
Correct |
9 ms |
6840 KB |
Output is correct |
33 |
Correct |
9 ms |
6860 KB |
Output is correct |
34 |
Correct |
8 ms |
6860 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
41 ms |
8796 KB |
Output is correct |
37 |
Correct |
45 ms |
9328 KB |
Output is correct |
38 |
Correct |
43 ms |
9356 KB |
Output is correct |
39 |
Correct |
44 ms |
9684 KB |
Output is correct |
40 |
Correct |
44 ms |
9660 KB |
Output is correct |
41 |
Correct |
7 ms |
6860 KB |
Output is correct |
42 |
Correct |
41 ms |
9240 KB |
Output is correct |
43 |
Correct |
44 ms |
9584 KB |
Output is correct |
44 |
Correct |
40 ms |
9580 KB |
Output is correct |
45 |
Correct |
38 ms |
9228 KB |
Output is correct |
46 |
Correct |
42 ms |
9688 KB |
Output is correct |
47 |
Correct |
41 ms |
9676 KB |
Output is correct |