#include "dna.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
namespace {
const int MAXN = 100'000;
int n;
int pre[3][3][MAXN + 10];
int ca[3], cb[3];
int cnt[3][3];
int ch2int(char ch) {
if(ch == 'A') return 0;
if(ch == 'T') return 1;
if(ch == 'C') return 2;
assert(false);
return -1;
}
void _init(string a, string b) {
n = sz(a);
For(c1, 0, 2) For(c2, 0, 2) pre[c1][c2][0] = 0;
For(i, 1, n) {
For(c1, 0, 2) For(c2, 0, 2) pre[c1][c2][i] = pre[c1][c2][i - 1];
int cha = ch2int(a[i - 1]);
int chb = ch2int(b[i - 1]);
pre[cha][chb][i]++;
}
}
int _get_distance(int l, int r) {
memset(ca, 0, sizeof(ca));
memset(cb, 0, sizeof(cb));
For(c1, 0, 2) For(c2, 0, 2) {
cnt[c1][c2] = pre[c1][c2][r] - pre[c1][c2][l - 1];
ca[c1] += cnt[c1][c2];
cb[c2] += cnt[c1][c2];
}
For(c, 0, 2) if(ca[c] != cb[c]) return -1;
int ans = 0;
auto owo = [&](int a, int b) {
int k = min(cnt[a][b], cnt[b][a]);
cnt[a][b] -= k;
cnt[b][a] -= k;
ans += k;
};
owo(0, 1);
owo(0, 2);
owo(1, 2);
return ans + max(cnt[0][1], cnt[1][0]) * 2;
}
}
void init(string a, string b) {
::_init(a, b);
}
int get_distance(int x, int y) {
return ::_get_distance(x + 1, y + 1);
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
2
1
-1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
5740 KB |
Output is correct |
2 |
Correct |
27 ms |
5712 KB |
Output is correct |
3 |
Correct |
33 ms |
5424 KB |
Output is correct |
4 |
Correct |
34 ms |
5708 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
4564 KB |
Output is correct |
5 |
Correct |
3 ms |
4564 KB |
Output is correct |
6 |
Correct |
4 ms |
4564 KB |
Output is correct |
7 |
Correct |
4 ms |
4308 KB |
Output is correct |
8 |
Correct |
3 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
4564 KB |
Output is correct |
5 |
Correct |
3 ms |
4564 KB |
Output is correct |
6 |
Correct |
4 ms |
4564 KB |
Output is correct |
7 |
Correct |
4 ms |
4308 KB |
Output is correct |
8 |
Correct |
3 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
27 ms |
5716 KB |
Output is correct |
11 |
Correct |
28 ms |
5716 KB |
Output is correct |
12 |
Correct |
29 ms |
5700 KB |
Output is correct |
13 |
Correct |
28 ms |
5856 KB |
Output is correct |
14 |
Correct |
29 ms |
6004 KB |
Output is correct |
15 |
Correct |
27 ms |
5900 KB |
Output is correct |
16 |
Correct |
27 ms |
5756 KB |
Output is correct |
17 |
Correct |
28 ms |
5832 KB |
Output is correct |
18 |
Correct |
28 ms |
5956 KB |
Output is correct |
19 |
Correct |
26 ms |
5832 KB |
Output is correct |
20 |
Correct |
27 ms |
5968 KB |
Output is correct |
21 |
Correct |
27 ms |
6112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
4564 KB |
Output is correct |
5 |
Correct |
3 ms |
4564 KB |
Output is correct |
6 |
Correct |
4 ms |
4564 KB |
Output is correct |
7 |
Correct |
4 ms |
4308 KB |
Output is correct |
8 |
Correct |
3 ms |
4564 KB |
Output is correct |
9 |
Correct |
4 ms |
4564 KB |
Output is correct |
10 |
Correct |
4 ms |
4180 KB |
Output is correct |
11 |
Correct |
5 ms |
4564 KB |
Output is correct |
12 |
Correct |
4 ms |
4308 KB |
Output is correct |
13 |
Correct |
4 ms |
4564 KB |
Output is correct |
14 |
Correct |
4 ms |
4564 KB |
Output is correct |
15 |
Correct |
3 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
5740 KB |
Output is correct |
2 |
Correct |
27 ms |
5712 KB |
Output is correct |
3 |
Correct |
33 ms |
5424 KB |
Output is correct |
4 |
Correct |
34 ms |
5708 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
3 ms |
4564 KB |
Output is correct |
12 |
Correct |
3 ms |
4564 KB |
Output is correct |
13 |
Correct |
4 ms |
4564 KB |
Output is correct |
14 |
Correct |
4 ms |
4308 KB |
Output is correct |
15 |
Correct |
3 ms |
4564 KB |
Output is correct |
16 |
Correct |
4 ms |
4564 KB |
Output is correct |
17 |
Correct |
27 ms |
5716 KB |
Output is correct |
18 |
Correct |
28 ms |
5716 KB |
Output is correct |
19 |
Correct |
29 ms |
5700 KB |
Output is correct |
20 |
Correct |
28 ms |
5856 KB |
Output is correct |
21 |
Correct |
29 ms |
6004 KB |
Output is correct |
22 |
Correct |
27 ms |
5900 KB |
Output is correct |
23 |
Correct |
27 ms |
5756 KB |
Output is correct |
24 |
Correct |
28 ms |
5832 KB |
Output is correct |
25 |
Correct |
28 ms |
5956 KB |
Output is correct |
26 |
Correct |
26 ms |
5832 KB |
Output is correct |
27 |
Correct |
27 ms |
5968 KB |
Output is correct |
28 |
Correct |
27 ms |
6112 KB |
Output is correct |
29 |
Correct |
4 ms |
4180 KB |
Output is correct |
30 |
Correct |
5 ms |
4564 KB |
Output is correct |
31 |
Correct |
4 ms |
4308 KB |
Output is correct |
32 |
Correct |
4 ms |
4564 KB |
Output is correct |
33 |
Correct |
4 ms |
4564 KB |
Output is correct |
34 |
Correct |
3 ms |
4564 KB |
Output is correct |
35 |
Correct |
0 ms |
340 KB |
Output is correct |
36 |
Correct |
28 ms |
5332 KB |
Output is correct |
37 |
Correct |
28 ms |
5724 KB |
Output is correct |
38 |
Correct |
33 ms |
5824 KB |
Output is correct |
39 |
Correct |
30 ms |
6948 KB |
Output is correct |
40 |
Correct |
33 ms |
6036 KB |
Output is correct |
41 |
Correct |
3 ms |
4564 KB |
Output is correct |
42 |
Correct |
30 ms |
6752 KB |
Output is correct |
43 |
Correct |
28 ms |
5984 KB |
Output is correct |
44 |
Correct |
28 ms |
6080 KB |
Output is correct |
45 |
Correct |
27 ms |
5856 KB |
Output is correct |
46 |
Correct |
27 ms |
6060 KB |
Output is correct |
47 |
Correct |
34 ms |
6036 KB |
Output is correct |