#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
int n, cnt[maxn][6], part[maxn][9];
void init(std::string s, std::string t) {
n = s.size();
for (int i = 1; i <= n; i++){
int x = (s[i-1] == 'A'? 0: (s[i-1] == 'T'? 1: 2));
int y = (t[i-1] == 'A'? 0: (t[i-1] == 'T'? 1: 2));
cnt[i][x]++;
cnt[i][y+3]++;
part[i][x*3+y]++;
}
for (int j = 0; j < 9; j++){
for (int i = 1; i <= n; i++){
part[i][j] += part[i-1][j];
if (j < 6) cnt[i][j] += cnt[i-1][j];
}
}
}
int get_distance(int x, int y) {
y++, x++;
for (int i = 0; i < 3; i++){
if (cnt[y][i] - cnt[x-1][i] != cnt[y][i+3] - cnt[x-1][i+3]) return -1;
}
int tmp[9];
for (int i = 0; i < 9; i++){
tmp[i] = part[y][i] - part[x-1][i];
// debug(i, tmp[i]);
}
int res = 0;
for (int i = 0; i < 9; i++){
int x = i / 3, y = i % 3;
int idx = y * 3 + x;
int val = min(tmp[i], tmp[idx]);
//debug(i, idx, val);
res += val;
tmp[i] -= val;
if (idx != i) tmp[idx] -= val;
}
assert(tmp[1] == tmp[5] && tmp[5] == tmp[6] && tmp[2] == tmp[7] && tmp[7] == tmp[3]);
res += tmp[1] + tmp[2];
return y - x + 1 - res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
9228 KB |
Output is correct |
2 |
Correct |
31 ms |
9352 KB |
Output is correct |
3 |
Correct |
30 ms |
8804 KB |
Output is correct |
4 |
Correct |
31 ms |
9368 KB |
Output is correct |
5 |
Correct |
1 ms |
308 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 |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6868 KB |
Output is correct |
5 |
Correct |
6 ms |
6848 KB |
Output is correct |
6 |
Correct |
6 ms |
6880 KB |
Output is correct |
7 |
Correct |
6 ms |
6396 KB |
Output is correct |
8 |
Correct |
6 ms |
6884 KB |
Output is correct |
9 |
Correct |
5 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6868 KB |
Output is correct |
5 |
Correct |
6 ms |
6848 KB |
Output is correct |
6 |
Correct |
6 ms |
6880 KB |
Output is correct |
7 |
Correct |
6 ms |
6396 KB |
Output is correct |
8 |
Correct |
6 ms |
6884 KB |
Output is correct |
9 |
Correct |
5 ms |
6868 KB |
Output is correct |
10 |
Correct |
33 ms |
9236 KB |
Output is correct |
11 |
Correct |
43 ms |
9292 KB |
Output is correct |
12 |
Correct |
47 ms |
9192 KB |
Output is correct |
13 |
Correct |
36 ms |
9464 KB |
Output is correct |
14 |
Correct |
32 ms |
9740 KB |
Output is correct |
15 |
Correct |
31 ms |
9600 KB |
Output is correct |
16 |
Correct |
42 ms |
9108 KB |
Output is correct |
17 |
Correct |
38 ms |
9356 KB |
Output is correct |
18 |
Correct |
34 ms |
9628 KB |
Output is correct |
19 |
Correct |
31 ms |
9284 KB |
Output is correct |
20 |
Correct |
38 ms |
9408 KB |
Output is correct |
21 |
Correct |
31 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
6868 KB |
Output is correct |
5 |
Correct |
6 ms |
6848 KB |
Output is correct |
6 |
Correct |
6 ms |
6880 KB |
Output is correct |
7 |
Correct |
6 ms |
6396 KB |
Output is correct |
8 |
Correct |
6 ms |
6884 KB |
Output is correct |
9 |
Correct |
5 ms |
6868 KB |
Output is correct |
10 |
Correct |
5 ms |
6340 KB |
Output is correct |
11 |
Correct |
6 ms |
6868 KB |
Output is correct |
12 |
Correct |
6 ms |
6484 KB |
Output is correct |
13 |
Correct |
6 ms |
6868 KB |
Output is correct |
14 |
Correct |
8 ms |
6848 KB |
Output is correct |
15 |
Correct |
5 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
9228 KB |
Output is correct |
2 |
Correct |
31 ms |
9352 KB |
Output is correct |
3 |
Correct |
30 ms |
8804 KB |
Output is correct |
4 |
Correct |
31 ms |
9368 KB |
Output is correct |
5 |
Correct |
1 ms |
308 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 |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
6 ms |
6868 KB |
Output is correct |
12 |
Correct |
6 ms |
6848 KB |
Output is correct |
13 |
Correct |
6 ms |
6880 KB |
Output is correct |
14 |
Correct |
6 ms |
6396 KB |
Output is correct |
15 |
Correct |
6 ms |
6884 KB |
Output is correct |
16 |
Correct |
5 ms |
6868 KB |
Output is correct |
17 |
Correct |
33 ms |
9236 KB |
Output is correct |
18 |
Correct |
43 ms |
9292 KB |
Output is correct |
19 |
Correct |
47 ms |
9192 KB |
Output is correct |
20 |
Correct |
36 ms |
9464 KB |
Output is correct |
21 |
Correct |
32 ms |
9740 KB |
Output is correct |
22 |
Correct |
31 ms |
9600 KB |
Output is correct |
23 |
Correct |
42 ms |
9108 KB |
Output is correct |
24 |
Correct |
38 ms |
9356 KB |
Output is correct |
25 |
Correct |
34 ms |
9628 KB |
Output is correct |
26 |
Correct |
31 ms |
9284 KB |
Output is correct |
27 |
Correct |
38 ms |
9408 KB |
Output is correct |
28 |
Correct |
31 ms |
9684 KB |
Output is correct |
29 |
Correct |
5 ms |
6340 KB |
Output is correct |
30 |
Correct |
6 ms |
6868 KB |
Output is correct |
31 |
Correct |
6 ms |
6484 KB |
Output is correct |
32 |
Correct |
6 ms |
6868 KB |
Output is correct |
33 |
Correct |
8 ms |
6848 KB |
Output is correct |
34 |
Correct |
5 ms |
6868 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
39 ms |
8748 KB |
Output is correct |
37 |
Correct |
33 ms |
9332 KB |
Output is correct |
38 |
Correct |
33 ms |
9328 KB |
Output is correct |
39 |
Correct |
33 ms |
9692 KB |
Output is correct |
40 |
Correct |
32 ms |
9716 KB |
Output is correct |
41 |
Correct |
5 ms |
6868 KB |
Output is correct |
42 |
Correct |
31 ms |
9184 KB |
Output is correct |
43 |
Correct |
31 ms |
9672 KB |
Output is correct |
44 |
Correct |
33 ms |
9592 KB |
Output is correct |
45 |
Correct |
30 ms |
9200 KB |
Output is correct |
46 |
Correct |
31 ms |
9608 KB |
Output is correct |
47 |
Correct |
31 ms |
9692 KB |
Output is correct |