# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
757764 |
2023-06-13T17:58:46 Z |
taher |
Mutating DNA (IOI21_dna) |
C++17 |
|
56 ms |
11768 KB |
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a, b, c, a_t, b_t, c_t;
vector<vector<int>> pref;
vector<char> q = {'A', 'T', 'C'};
void init(string s, string t) {
n = (int)s.length();
a.resize(n + 1); b.resize(n + 1); c.resize(n + 1); a_t.resize(n + 1); b_t.resize(n + 1); c_t.resize(n + 1); pref.resize(n + 1, vector<int>(6));
for (int i = 0 ; i < n ; i++) {
int cnt = 0;
for (int j = 0 ; j < (int)q.size() ; j++) {
for (int m = 0 ; m < (int)q.size() ; m++) {
char one = q[j], two = q[m];
if (one == two) continue;
pref[i + 1][cnt] = pref[i][cnt] + (s[i] == one && t[i] == two);
cnt++;
}
}
}
for (int i = 0 ; i < n ; i++) {
a[i + 1] = a[i] + (s[i] == 'A');
a_t[i + 1] = a_t[i] + (t[i] == 'A');
b[i + 1] = b[i] + (s[i] == 'T');
b_t[i + 1] = b_t[i] + (t[i] == 'T');
c[i + 1] = c[i] + (s[i] == 'C');
c_t[i + 1] = c_t[i] + (t[i] == 'C');
}
return ;
}
int get_distance(int x, int y) {
if (a[y + 1] - a[x] == a_t[y + 1] - a_t[x] && b[y + 1] - b[x] == b_t[y + 1] - b_t[x] && c[y + 1] - c[x] == c_t[y + 1] - c_t[x]) {
int AT = pref[y+1][0]-pref[x][0], AC = pref[y+1][1]-pref[x][1], TA = pref[y+1][2]-pref[x][2], TC = pref[y+1][3] -pref[x][3], CA = pref[y+1][4] - pref[x][4], CT = pref[y+1][5] - pref[x][5];
int best = min(AT, TA) + min(AC, CA) + (max(AT, TA) - min(AT, TA)) * 2 + min(CT, TC);
return best;
}
else return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
11216 KB |
Output is correct |
2 |
Correct |
46 ms |
11312 KB |
Output is correct |
3 |
Correct |
53 ms |
10588 KB |
Output is correct |
4 |
Correct |
47 ms |
11384 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
8740 KB |
Output is correct |
5 |
Correct |
11 ms |
8916 KB |
Output is correct |
6 |
Correct |
11 ms |
8788 KB |
Output is correct |
7 |
Correct |
10 ms |
8276 KB |
Output is correct |
8 |
Correct |
11 ms |
8936 KB |
Output is correct |
9 |
Correct |
12 ms |
8840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
8740 KB |
Output is correct |
5 |
Correct |
11 ms |
8916 KB |
Output is correct |
6 |
Correct |
11 ms |
8788 KB |
Output is correct |
7 |
Correct |
10 ms |
8276 KB |
Output is correct |
8 |
Correct |
11 ms |
8936 KB |
Output is correct |
9 |
Correct |
12 ms |
8840 KB |
Output is correct |
10 |
Correct |
43 ms |
11212 KB |
Output is correct |
11 |
Correct |
44 ms |
11460 KB |
Output is correct |
12 |
Correct |
43 ms |
11024 KB |
Output is correct |
13 |
Correct |
43 ms |
11368 KB |
Output is correct |
14 |
Correct |
44 ms |
11700 KB |
Output is correct |
15 |
Correct |
56 ms |
11704 KB |
Output is correct |
16 |
Correct |
39 ms |
11056 KB |
Output is correct |
17 |
Correct |
43 ms |
11268 KB |
Output is correct |
18 |
Correct |
41 ms |
11684 KB |
Output is correct |
19 |
Correct |
39 ms |
11084 KB |
Output is correct |
20 |
Correct |
39 ms |
11248 KB |
Output is correct |
21 |
Correct |
41 ms |
11712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
8740 KB |
Output is correct |
5 |
Correct |
11 ms |
8916 KB |
Output is correct |
6 |
Correct |
11 ms |
8788 KB |
Output is correct |
7 |
Correct |
10 ms |
8276 KB |
Output is correct |
8 |
Correct |
11 ms |
8936 KB |
Output is correct |
9 |
Correct |
12 ms |
8840 KB |
Output is correct |
10 |
Correct |
10 ms |
8148 KB |
Output is correct |
11 |
Correct |
12 ms |
8916 KB |
Output is correct |
12 |
Correct |
12 ms |
8276 KB |
Output is correct |
13 |
Correct |
14 ms |
8888 KB |
Output is correct |
14 |
Correct |
12 ms |
8844 KB |
Output is correct |
15 |
Correct |
11 ms |
8916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
11216 KB |
Output is correct |
2 |
Correct |
46 ms |
11312 KB |
Output is correct |
3 |
Correct |
53 ms |
10588 KB |
Output is correct |
4 |
Correct |
47 ms |
11384 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
13 ms |
8740 KB |
Output is correct |
12 |
Correct |
11 ms |
8916 KB |
Output is correct |
13 |
Correct |
11 ms |
8788 KB |
Output is correct |
14 |
Correct |
10 ms |
8276 KB |
Output is correct |
15 |
Correct |
11 ms |
8936 KB |
Output is correct |
16 |
Correct |
12 ms |
8840 KB |
Output is correct |
17 |
Correct |
43 ms |
11212 KB |
Output is correct |
18 |
Correct |
44 ms |
11460 KB |
Output is correct |
19 |
Correct |
43 ms |
11024 KB |
Output is correct |
20 |
Correct |
43 ms |
11368 KB |
Output is correct |
21 |
Correct |
44 ms |
11700 KB |
Output is correct |
22 |
Correct |
56 ms |
11704 KB |
Output is correct |
23 |
Correct |
39 ms |
11056 KB |
Output is correct |
24 |
Correct |
43 ms |
11268 KB |
Output is correct |
25 |
Correct |
41 ms |
11684 KB |
Output is correct |
26 |
Correct |
39 ms |
11084 KB |
Output is correct |
27 |
Correct |
39 ms |
11248 KB |
Output is correct |
28 |
Correct |
41 ms |
11712 KB |
Output is correct |
29 |
Correct |
10 ms |
8148 KB |
Output is correct |
30 |
Correct |
12 ms |
8916 KB |
Output is correct |
31 |
Correct |
12 ms |
8276 KB |
Output is correct |
32 |
Correct |
14 ms |
8888 KB |
Output is correct |
33 |
Correct |
12 ms |
8844 KB |
Output is correct |
34 |
Correct |
11 ms |
8916 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
39 ms |
10572 KB |
Output is correct |
37 |
Correct |
43 ms |
11436 KB |
Output is correct |
38 |
Correct |
43 ms |
11292 KB |
Output is correct |
39 |
Correct |
44 ms |
11724 KB |
Output is correct |
40 |
Correct |
42 ms |
11768 KB |
Output is correct |
41 |
Correct |
10 ms |
8924 KB |
Output is correct |
42 |
Correct |
38 ms |
11176 KB |
Output is correct |
43 |
Correct |
45 ms |
11700 KB |
Output is correct |
44 |
Correct |
47 ms |
11652 KB |
Output is correct |
45 |
Correct |
38 ms |
11124 KB |
Output is correct |
46 |
Correct |
40 ms |
11700 KB |
Output is correct |
47 |
Correct |
39 ms |
11724 KB |
Output is correct |