# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
764634 |
2023-06-23T17:06:00 Z |
ind1v |
Mutating DNA (IOI21_dna) |
C++17 |
|
35 ms |
9788 KB |
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int N = 100005;
int n;
int aca[N], acc[N], act[N];
int bca[N], bcc[N], bct[N];
int cnt[N][3][3];
int comp(int x) {
if (x == 0) {
return 0;
}
if (x == 2) {
return 1;
}
if (x == 19) {
return 2;
}
}
void init(string a, string b) {
n = a.size();
a = '#' + a;
b = '#' + b;
for (int i = 1; i <= n; i++) {
a[i] -= 'A' - 'a';
b[i] -= 'A' - 'a';
}
for (int i = 1; i <= n; i++) {
if (a[i] == 'a') {
aca[i] = 1;
} else if (a[i] == 'c') {
acc[i] = 1;
} else {
act[i] = 1;
}
if (b[i] == 'a') {
bca[i] = 1;
} else if (b[i] == 'c') {
bcc[i] = 1;
} else {
bct[i] = 1;
}
cnt[i][comp(a[i] - 'a')][comp(b[i] - 'a')] = 1;
}
partial_sum(aca + 1, aca + n + 1, aca + 1);
partial_sum(acc + 1, acc + n + 1, acc + 1);
partial_sum(act + 1, act + n + 1, act + 1);
partial_sum(bca + 1, bca + n + 1, bca + 1);
partial_sum(bcc + 1, bcc + n + 1, bcc + 1);
partial_sum(bct + 1, bct + n + 1, bct + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
cnt[i][j][k] += cnt[i - 1][j][k];
}
}
}
}
int get_distance(int x, int y) {
++x; ++y;
int tot_a = aca[y] - aca[x - 1] - (bca[y] - bca[x - 1]);
int tot_c = acc[y] - acc[x - 1] - (bcc[y] - bcc[x - 1]);
int tot_t = act[y] - act[x - 1] - (bct[y] - bct[x - 1]);
if (tot_a != 0 || tot_c != 0 || tot_t != 0) {
return -1;
}
int cnt_ac = cnt[y][0][1] - cnt[x - 1][0][1];
int cnt_at = cnt[y][0][2] - cnt[x - 1][0][2];
int cnt_ca = cnt[y][1][0] - cnt[x - 1][1][0];
int cnt_ct = cnt[y][1][2] - cnt[x - 1][1][2];
int cnt_ta = cnt[y][2][0] - cnt[x - 1][2][0];
int cnt_tc = cnt[y][2][1] - cnt[x - 1][2][1];
int ans = 0;
int mn = min(cnt_ac, cnt_ca);
ans += mn;
cnt_ac -= mn;
cnt_ca -= mn;
mn = min(cnt_at, cnt_ta);
ans += mn;
cnt_at -= mn;
cnt_ta -= mn;
mn = min(cnt_ct, cnt_tc);
ans += mn;
cnt_ct -= mn;
cnt_tc -= mn;
ans += (cnt_ac + cnt_at + cnt_ca + cnt_ct + cnt_ta + cnt_tc) / 3 * 2;
return ans;
}
Compilation message
dna.cpp: In function 'int comp(int)':
dna.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
23 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
7976 KB |
Output is correct |
2 |
Correct |
29 ms |
8012 KB |
Output is correct |
3 |
Correct |
28 ms |
7444 KB |
Output is correct |
4 |
Correct |
29 ms |
9384 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6740 KB |
Output is correct |
5 |
Correct |
6 ms |
6740 KB |
Output is correct |
6 |
Correct |
5 ms |
6740 KB |
Output is correct |
7 |
Correct |
5 ms |
6356 KB |
Output is correct |
8 |
Correct |
5 ms |
6740 KB |
Output is correct |
9 |
Correct |
4 ms |
6740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6740 KB |
Output is correct |
5 |
Correct |
6 ms |
6740 KB |
Output is correct |
6 |
Correct |
5 ms |
6740 KB |
Output is correct |
7 |
Correct |
5 ms |
6356 KB |
Output is correct |
8 |
Correct |
5 ms |
6740 KB |
Output is correct |
9 |
Correct |
4 ms |
6740 KB |
Output is correct |
10 |
Correct |
30 ms |
7932 KB |
Output is correct |
11 |
Correct |
28 ms |
8020 KB |
Output is correct |
12 |
Correct |
29 ms |
7968 KB |
Output is correct |
13 |
Correct |
35 ms |
8116 KB |
Output is correct |
14 |
Correct |
30 ms |
8376 KB |
Output is correct |
15 |
Correct |
28 ms |
8228 KB |
Output is correct |
16 |
Correct |
28 ms |
7956 KB |
Output is correct |
17 |
Correct |
28 ms |
8048 KB |
Output is correct |
18 |
Correct |
29 ms |
8356 KB |
Output is correct |
19 |
Correct |
26 ms |
8004 KB |
Output is correct |
20 |
Correct |
27 ms |
8132 KB |
Output is correct |
21 |
Correct |
27 ms |
8364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6740 KB |
Output is correct |
5 |
Correct |
6 ms |
6740 KB |
Output is correct |
6 |
Correct |
5 ms |
6740 KB |
Output is correct |
7 |
Correct |
5 ms |
6356 KB |
Output is correct |
8 |
Correct |
5 ms |
6740 KB |
Output is correct |
9 |
Correct |
4 ms |
6740 KB |
Output is correct |
10 |
Correct |
5 ms |
6228 KB |
Output is correct |
11 |
Correct |
6 ms |
6996 KB |
Output is correct |
12 |
Correct |
5 ms |
6608 KB |
Output is correct |
13 |
Correct |
5 ms |
6996 KB |
Output is correct |
14 |
Correct |
6 ms |
6980 KB |
Output is correct |
15 |
Correct |
5 ms |
6972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
7976 KB |
Output is correct |
2 |
Correct |
29 ms |
8012 KB |
Output is correct |
3 |
Correct |
28 ms |
7444 KB |
Output is correct |
4 |
Correct |
29 ms |
9384 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
6 ms |
6740 KB |
Output is correct |
12 |
Correct |
6 ms |
6740 KB |
Output is correct |
13 |
Correct |
5 ms |
6740 KB |
Output is correct |
14 |
Correct |
5 ms |
6356 KB |
Output is correct |
15 |
Correct |
5 ms |
6740 KB |
Output is correct |
16 |
Correct |
4 ms |
6740 KB |
Output is correct |
17 |
Correct |
30 ms |
7932 KB |
Output is correct |
18 |
Correct |
28 ms |
8020 KB |
Output is correct |
19 |
Correct |
29 ms |
7968 KB |
Output is correct |
20 |
Correct |
35 ms |
8116 KB |
Output is correct |
21 |
Correct |
30 ms |
8376 KB |
Output is correct |
22 |
Correct |
28 ms |
8228 KB |
Output is correct |
23 |
Correct |
28 ms |
7956 KB |
Output is correct |
24 |
Correct |
28 ms |
8048 KB |
Output is correct |
25 |
Correct |
29 ms |
8356 KB |
Output is correct |
26 |
Correct |
26 ms |
8004 KB |
Output is correct |
27 |
Correct |
27 ms |
8132 KB |
Output is correct |
28 |
Correct |
27 ms |
8364 KB |
Output is correct |
29 |
Correct |
5 ms |
6228 KB |
Output is correct |
30 |
Correct |
6 ms |
6996 KB |
Output is correct |
31 |
Correct |
5 ms |
6608 KB |
Output is correct |
32 |
Correct |
5 ms |
6996 KB |
Output is correct |
33 |
Correct |
6 ms |
6980 KB |
Output is correct |
34 |
Correct |
5 ms |
6972 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
8844 KB |
Output is correct |
37 |
Correct |
28 ms |
9384 KB |
Output is correct |
38 |
Correct |
30 ms |
9400 KB |
Output is correct |
39 |
Correct |
30 ms |
9760 KB |
Output is correct |
40 |
Correct |
29 ms |
9768 KB |
Output is correct |
41 |
Correct |
4 ms |
6996 KB |
Output is correct |
42 |
Correct |
28 ms |
9224 KB |
Output is correct |
43 |
Correct |
29 ms |
9648 KB |
Output is correct |
44 |
Correct |
29 ms |
9640 KB |
Output is correct |
45 |
Correct |
28 ms |
9320 KB |
Output is correct |
46 |
Correct |
28 ms |
9788 KB |
Output is correct |
47 |
Correct |
28 ms |
9640 KB |
Output is correct |