# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
898403 |
2024-01-04T15:48:30 Z |
aqxa |
Mutating DNA (IOI21_dna) |
C++17 |
|
55 ms |
9760 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int pa[N][3], pb[N][3], n, p[N][3][3], c[3][3];
void init(string a, string b) {
n = a.size();
for (int i = 0; i < n; ++i) {
int ca = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2));
int cb = (b[i] == 'A' ? 0 : (b[i] == 'T' ? 1 : 2));
pa[i + 1][ca]++;
pb[i + 1][cb]++;
p[i + 1][ca][cb]++;
for (int j = 0; j < 3; ++j) {
pa[i + 1][j] += pa[i][j];
pb[i + 1][j] += pb[i][j];
for (int k = 0; k < 3; ++k) {
p[i + 1][j][k] += p[i][j][k];
}
}
}
}
int get_distance(int x, int y) {
for (int i = 0; i < 3; ++i) {
if (pa[y + 1][i] - pa[x][i] != pb[y + 1][i] - pb[x][i]) {
return -1;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
c[i][j] = p[y + 1][i][j] - p[x][i][j];
}
}
int ans = 0;
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
int z = min(c[i][j], c[j][i]);
c[i][j] -= z;
c[j][i] -= z;
ans += z;
}
}
vector<int> d0, d1;
for (int i = 0; i < 3; ++i) {
d0.push_back(c[i][(i + 1) % 3]);
d1.push_back(c[i][(i + 2) % 3]);
}
sort(d0.begin(), d0.end());
sort(d1.begin(), d1.end());
assert(d0[0] == d0[2] && d1[0] == d1[2]);
assert(d0[0] == 0 || d1[0] == 0);
return 2 * (d0[0] + d1[0]) + ans;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int m, q;
// cin >> m >> q;
// string a, b;
// for (int i = 0; i < m; ++i) {
// int c = rand() % 3;
// if (c == 0) a += 'A';
// if (c == 1) a += 'T';
// if (c == 2) a += 'C';
// }
// b = a;
// random_shuffle(b.begin(), b.end());
// init(a, b);
// cout << a << "\n";
// cout << b << "\n";
// for (int i = 0; i < m; ++i) {
// for (int j = i; j < m; ++j) {
// cout << "! " << i << ' ' << j << ' ' << get_distance(i, j) << '\n';
// }
// }
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
9492 KB |
Output is correct |
2 |
Correct |
55 ms |
9348 KB |
Output is correct |
3 |
Correct |
39 ms |
9104 KB |
Output is correct |
4 |
Correct |
39 ms |
9352 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
4 ms |
7004 KB |
Output is correct |
5 |
Correct |
5 ms |
6860 KB |
Output is correct |
6 |
Correct |
5 ms |
7004 KB |
Output is correct |
7 |
Correct |
4 ms |
6872 KB |
Output is correct |
8 |
Correct |
4 ms |
6980 KB |
Output is correct |
9 |
Correct |
3 ms |
7000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
4 ms |
7004 KB |
Output is correct |
5 |
Correct |
5 ms |
6860 KB |
Output is correct |
6 |
Correct |
5 ms |
7004 KB |
Output is correct |
7 |
Correct |
4 ms |
6872 KB |
Output is correct |
8 |
Correct |
4 ms |
6980 KB |
Output is correct |
9 |
Correct |
3 ms |
7000 KB |
Output is correct |
10 |
Correct |
39 ms |
9492 KB |
Output is correct |
11 |
Correct |
40 ms |
9364 KB |
Output is correct |
12 |
Correct |
39 ms |
9644 KB |
Output is correct |
13 |
Correct |
45 ms |
9752 KB |
Output is correct |
14 |
Correct |
40 ms |
9728 KB |
Output is correct |
15 |
Correct |
44 ms |
9616 KB |
Output is correct |
16 |
Correct |
40 ms |
9412 KB |
Output is correct |
17 |
Correct |
39 ms |
9500 KB |
Output is correct |
18 |
Correct |
51 ms |
9744 KB |
Output is correct |
19 |
Correct |
39 ms |
9508 KB |
Output is correct |
20 |
Correct |
40 ms |
9492 KB |
Output is correct |
21 |
Correct |
39 ms |
9604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
4 ms |
7004 KB |
Output is correct |
5 |
Correct |
5 ms |
6860 KB |
Output is correct |
6 |
Correct |
5 ms |
7004 KB |
Output is correct |
7 |
Correct |
4 ms |
6872 KB |
Output is correct |
8 |
Correct |
4 ms |
6980 KB |
Output is correct |
9 |
Correct |
3 ms |
7000 KB |
Output is correct |
10 |
Correct |
3 ms |
6740 KB |
Output is correct |
11 |
Correct |
3 ms |
7004 KB |
Output is correct |
12 |
Correct |
3 ms |
6872 KB |
Output is correct |
13 |
Correct |
4 ms |
7004 KB |
Output is correct |
14 |
Correct |
3 ms |
7004 KB |
Output is correct |
15 |
Correct |
3 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
9492 KB |
Output is correct |
2 |
Correct |
55 ms |
9348 KB |
Output is correct |
3 |
Correct |
39 ms |
9104 KB |
Output is correct |
4 |
Correct |
39 ms |
9352 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
4 ms |
7004 KB |
Output is correct |
12 |
Correct |
5 ms |
6860 KB |
Output is correct |
13 |
Correct |
5 ms |
7004 KB |
Output is correct |
14 |
Correct |
4 ms |
6872 KB |
Output is correct |
15 |
Correct |
4 ms |
6980 KB |
Output is correct |
16 |
Correct |
3 ms |
7000 KB |
Output is correct |
17 |
Correct |
39 ms |
9492 KB |
Output is correct |
18 |
Correct |
40 ms |
9364 KB |
Output is correct |
19 |
Correct |
39 ms |
9644 KB |
Output is correct |
20 |
Correct |
45 ms |
9752 KB |
Output is correct |
21 |
Correct |
40 ms |
9728 KB |
Output is correct |
22 |
Correct |
44 ms |
9616 KB |
Output is correct |
23 |
Correct |
40 ms |
9412 KB |
Output is correct |
24 |
Correct |
39 ms |
9500 KB |
Output is correct |
25 |
Correct |
51 ms |
9744 KB |
Output is correct |
26 |
Correct |
39 ms |
9508 KB |
Output is correct |
27 |
Correct |
40 ms |
9492 KB |
Output is correct |
28 |
Correct |
39 ms |
9604 KB |
Output is correct |
29 |
Correct |
3 ms |
6740 KB |
Output is correct |
30 |
Correct |
3 ms |
7004 KB |
Output is correct |
31 |
Correct |
3 ms |
6872 KB |
Output is correct |
32 |
Correct |
4 ms |
7004 KB |
Output is correct |
33 |
Correct |
3 ms |
7004 KB |
Output is correct |
34 |
Correct |
3 ms |
7004 KB |
Output is correct |
35 |
Correct |
1 ms |
2392 KB |
Output is correct |
36 |
Correct |
41 ms |
9076 KB |
Output is correct |
37 |
Correct |
41 ms |
9484 KB |
Output is correct |
38 |
Correct |
53 ms |
9500 KB |
Output is correct |
39 |
Correct |
39 ms |
9740 KB |
Output is correct |
40 |
Correct |
40 ms |
9744 KB |
Output is correct |
41 |
Correct |
3 ms |
7000 KB |
Output is correct |
42 |
Correct |
39 ms |
9500 KB |
Output is correct |
43 |
Correct |
52 ms |
9760 KB |
Output is correct |
44 |
Correct |
43 ms |
9592 KB |
Output is correct |
45 |
Correct |
38 ms |
9496 KB |
Output is correct |
46 |
Correct |
38 ms |
9740 KB |
Output is correct |
47 |
Correct |
39 ms |
9752 KB |
Output is correct |