# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
563760 |
2022-05-18T05:30:12 Z |
kartel |
Mutating DNA (IOI21_dna) |
C++17 |
|
184 ms |
8680 KB |
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "dna.h"
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define el "\n"
using namespace std;
const int N = 2e5 + 500;
vector <int> in_a[26], in_b[26];
int pf[3][3][N];
int n;
vector <char> sb;
void init(string a, string b) {
n = sz(a);
map <char, int> mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for (int i = 0; i < sz(a); i++) {
in_a[a[i] - 'A'].pb(i);
in_b[b[i] - 'A'].pb(i);
pf[mp[a[i]]][mp[b[i]]][i]++;
}
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
for (int i = 1; i < n; i++) {
pf[a][b][i] += pf[a][b][i - 1];
}
}
}
sb = {'A', 'C', 'T'};
}
int get_distance(int x, int y) {
for (auto c : sb) {
int L = lower_bound(all(in_a[c - 'A']), x) - in_a[c - 'A'].begin();
int R = upper_bound(all(in_a[c - 'A']), y) - in_a[c - 'A'].begin();
int l = lower_bound(all(in_b[c - 'A']), x) - in_b[c - 'A'].begin();
int r = upper_bound(all(in_b[c - 'A']), y) - in_b[c - 'A'].begin();
if (R - L != r - l) {
return -1;
}
}
vector <vector <int> > cnt(3, vector <int> (3, 0));
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
cnt[a][b] = pf[a][b][y] - (x ? pf[a][b][x - 1] : 0);
}
}
int ans = 0;
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (a == b) {
continue;
}
int cur = min(cnt[a][b], cnt[b][a]);
ans += cur;
cnt[a][a] += cur; cnt[a][b] -= cur;
cnt[b][b] += cur; cnt[b][a] -= cur;
}
}
int add = 0;
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
if (a == b) {
continue;
}
add += cnt[a][b];
}
}
assert(add % 3 == 0);
return ans + add - add / 3;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
7972 KB |
Output is correct |
2 |
Correct |
141 ms |
7956 KB |
Output is correct |
3 |
Correct |
170 ms |
7636 KB |
Output is correct |
4 |
Correct |
184 ms |
8124 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
10 ms |
5436 KB |
Output is correct |
5 |
Correct |
10 ms |
5560 KB |
Output is correct |
6 |
Correct |
9 ms |
5500 KB |
Output is correct |
7 |
Correct |
9 ms |
5216 KB |
Output is correct |
8 |
Correct |
10 ms |
5584 KB |
Output is correct |
9 |
Correct |
10 ms |
5540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
10 ms |
5436 KB |
Output is correct |
5 |
Correct |
10 ms |
5560 KB |
Output is correct |
6 |
Correct |
9 ms |
5500 KB |
Output is correct |
7 |
Correct |
9 ms |
5216 KB |
Output is correct |
8 |
Correct |
10 ms |
5584 KB |
Output is correct |
9 |
Correct |
10 ms |
5540 KB |
Output is correct |
10 |
Correct |
137 ms |
7968 KB |
Output is correct |
11 |
Correct |
137 ms |
7960 KB |
Output is correct |
12 |
Correct |
134 ms |
8164 KB |
Output is correct |
13 |
Correct |
146 ms |
8172 KB |
Output is correct |
14 |
Correct |
145 ms |
8400 KB |
Output is correct |
15 |
Correct |
136 ms |
8260 KB |
Output is correct |
16 |
Correct |
119 ms |
8076 KB |
Output is correct |
17 |
Correct |
126 ms |
8092 KB |
Output is correct |
18 |
Correct |
125 ms |
8332 KB |
Output is correct |
19 |
Correct |
101 ms |
7892 KB |
Output is correct |
20 |
Correct |
100 ms |
8012 KB |
Output is correct |
21 |
Correct |
101 ms |
8404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
10 ms |
5436 KB |
Output is correct |
5 |
Correct |
10 ms |
5560 KB |
Output is correct |
6 |
Correct |
9 ms |
5500 KB |
Output is correct |
7 |
Correct |
9 ms |
5216 KB |
Output is correct |
8 |
Correct |
10 ms |
5584 KB |
Output is correct |
9 |
Correct |
10 ms |
5540 KB |
Output is correct |
10 |
Correct |
9 ms |
5204 KB |
Output is correct |
11 |
Correct |
10 ms |
5748 KB |
Output is correct |
12 |
Correct |
10 ms |
5312 KB |
Output is correct |
13 |
Correct |
11 ms |
5836 KB |
Output is correct |
14 |
Correct |
12 ms |
5780 KB |
Output is correct |
15 |
Correct |
9 ms |
5696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
7972 KB |
Output is correct |
2 |
Correct |
141 ms |
7956 KB |
Output is correct |
3 |
Correct |
170 ms |
7636 KB |
Output is correct |
4 |
Correct |
184 ms |
8124 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
10 ms |
5436 KB |
Output is correct |
12 |
Correct |
10 ms |
5560 KB |
Output is correct |
13 |
Correct |
9 ms |
5500 KB |
Output is correct |
14 |
Correct |
9 ms |
5216 KB |
Output is correct |
15 |
Correct |
10 ms |
5584 KB |
Output is correct |
16 |
Correct |
10 ms |
5540 KB |
Output is correct |
17 |
Correct |
137 ms |
7968 KB |
Output is correct |
18 |
Correct |
137 ms |
7960 KB |
Output is correct |
19 |
Correct |
134 ms |
8164 KB |
Output is correct |
20 |
Correct |
146 ms |
8172 KB |
Output is correct |
21 |
Correct |
145 ms |
8400 KB |
Output is correct |
22 |
Correct |
136 ms |
8260 KB |
Output is correct |
23 |
Correct |
119 ms |
8076 KB |
Output is correct |
24 |
Correct |
126 ms |
8092 KB |
Output is correct |
25 |
Correct |
125 ms |
8332 KB |
Output is correct |
26 |
Correct |
101 ms |
7892 KB |
Output is correct |
27 |
Correct |
100 ms |
8012 KB |
Output is correct |
28 |
Correct |
101 ms |
8404 KB |
Output is correct |
29 |
Correct |
9 ms |
5204 KB |
Output is correct |
30 |
Correct |
10 ms |
5748 KB |
Output is correct |
31 |
Correct |
10 ms |
5312 KB |
Output is correct |
32 |
Correct |
11 ms |
5836 KB |
Output is correct |
33 |
Correct |
12 ms |
5780 KB |
Output is correct |
34 |
Correct |
9 ms |
5696 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
162 ms |
7680 KB |
Output is correct |
37 |
Correct |
174 ms |
8244 KB |
Output is correct |
38 |
Correct |
167 ms |
8172 KB |
Output is correct |
39 |
Correct |
159 ms |
8540 KB |
Output is correct |
40 |
Correct |
165 ms |
8628 KB |
Output is correct |
41 |
Correct |
10 ms |
5564 KB |
Output is correct |
42 |
Correct |
151 ms |
8264 KB |
Output is correct |
43 |
Correct |
157 ms |
8460 KB |
Output is correct |
44 |
Correct |
155 ms |
8680 KB |
Output is correct |
45 |
Correct |
125 ms |
8064 KB |
Output is correct |
46 |
Correct |
120 ms |
8516 KB |
Output is correct |
47 |
Correct |
122 ms |
8344 KB |
Output is correct |