#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
// Templates
// ==============================================
// Debugging
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
typedef long long ll;
typedef vector<int> VI;
typedef vector<long long> VLL;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<pair<int, int>> VPI;
#define pb push_back
#define ff first
#define ss second
#define loop(i, s, e) for (int i = s; i < e; ++i)
#define inp(v) for (auto& x : v) cin >> x
#define all(a) a.begin(), a.end()
#define revall(a) a.rbegin(), a.rend()
#define nl "\n"
// #define MOD 998244353
#define MOD 1000000007
#define MAXN 300002
#define INF (int) 1e9
#define INFL (ll) 1e18
#define yep cout << "YES\n"
#define nope cout << "NO\n"
// ==============================================
#define AB 0
#define BC 1
#define CA 2
#define BA 3
#define CB 4
#define AC 5
#define get(l, r, x) pre[r + 1][x] - pre[l][x]
VVI pre;
void init(std::string a, std::string b)
{
int n = a.size();
pre.resize(n + 1, VI(6));
loop(i, 0, n)
{
pre[i + 1][AB] = pre[i][AB] + (make_pair(a[i], b[i]) == make_pair('A', 'T'));
pre[i + 1][AC] = pre[i][AC] + (make_pair(a[i], b[i]) == make_pair('A', 'C'));
pre[i + 1][CB] = pre[i][CB] + (make_pair(a[i], b[i]) == make_pair('C', 'T'));
pre[i + 1][BC] = pre[i][BC] + (make_pair(a[i], b[i]) == make_pair('T', 'C'));
pre[i + 1][BA] = pre[i][BA] + (make_pair(a[i], b[i]) == make_pair('T', 'A'));
pre[i + 1][CA] = pre[i][CA] + (make_pair(a[i], b[i]) == make_pair('C', 'A'));
}
}
int get_distance(int x, int y)
{
int cnt[6];
loop(i, 0, 6) cnt[i] = get(x, y, i);
int ans = 0;
loop(i, 0, 3)
{
int mn = min(cnt[i], cnt[i + 3]);
cnt[i] -= mn;
cnt[i + 3] -= mn;
ans += mn;
}
if (cnt[0] == cnt[1] && cnt[1] == cnt[2] && cnt[3] == cnt[4] && cnt[4] == cnt[5])
{
ans += 2 * max(cnt[0], cnt[3]);
return ans;
}
else return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
7772 KB |
Output is correct |
2 |
Correct |
29 ms |
8584 KB |
Output is correct |
3 |
Correct |
29 ms |
8016 KB |
Output is correct |
4 |
Correct |
30 ms |
8380 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
6492 KB |
Output is correct |
5 |
Correct |
8 ms |
6512 KB |
Output is correct |
6 |
Correct |
7 ms |
6492 KB |
Output is correct |
7 |
Correct |
6 ms |
6092 KB |
Output is correct |
8 |
Correct |
6 ms |
6492 KB |
Output is correct |
9 |
Correct |
6 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
6492 KB |
Output is correct |
5 |
Correct |
8 ms |
6512 KB |
Output is correct |
6 |
Correct |
7 ms |
6492 KB |
Output is correct |
7 |
Correct |
6 ms |
6092 KB |
Output is correct |
8 |
Correct |
6 ms |
6492 KB |
Output is correct |
9 |
Correct |
6 ms |
6492 KB |
Output is correct |
10 |
Correct |
30 ms |
8384 KB |
Output is correct |
11 |
Correct |
30 ms |
8564 KB |
Output is correct |
12 |
Correct |
30 ms |
8704 KB |
Output is correct |
13 |
Correct |
30 ms |
8672 KB |
Output is correct |
14 |
Correct |
31 ms |
9044 KB |
Output is correct |
15 |
Correct |
30 ms |
8276 KB |
Output is correct |
16 |
Correct |
29 ms |
8532 KB |
Output is correct |
17 |
Correct |
30 ms |
8276 KB |
Output is correct |
18 |
Correct |
32 ms |
8952 KB |
Output is correct |
19 |
Correct |
28 ms |
8788 KB |
Output is correct |
20 |
Correct |
31 ms |
8528 KB |
Output is correct |
21 |
Correct |
35 ms |
8892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
6492 KB |
Output is correct |
5 |
Correct |
8 ms |
6512 KB |
Output is correct |
6 |
Correct |
7 ms |
6492 KB |
Output is correct |
7 |
Correct |
6 ms |
6092 KB |
Output is correct |
8 |
Correct |
6 ms |
6492 KB |
Output is correct |
9 |
Correct |
6 ms |
6492 KB |
Output is correct |
10 |
Correct |
6 ms |
5976 KB |
Output is correct |
11 |
Correct |
9 ms |
6488 KB |
Output is correct |
12 |
Correct |
6 ms |
6236 KB |
Output is correct |
13 |
Correct |
6 ms |
6492 KB |
Output is correct |
14 |
Correct |
7 ms |
6488 KB |
Output is correct |
15 |
Correct |
6 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
7772 KB |
Output is correct |
2 |
Correct |
29 ms |
8584 KB |
Output is correct |
3 |
Correct |
29 ms |
8016 KB |
Output is correct |
4 |
Correct |
30 ms |
8380 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
6 ms |
6492 KB |
Output is correct |
12 |
Correct |
8 ms |
6512 KB |
Output is correct |
13 |
Correct |
7 ms |
6492 KB |
Output is correct |
14 |
Correct |
6 ms |
6092 KB |
Output is correct |
15 |
Correct |
6 ms |
6492 KB |
Output is correct |
16 |
Correct |
6 ms |
6492 KB |
Output is correct |
17 |
Correct |
30 ms |
8384 KB |
Output is correct |
18 |
Correct |
30 ms |
8564 KB |
Output is correct |
19 |
Correct |
30 ms |
8704 KB |
Output is correct |
20 |
Correct |
30 ms |
8672 KB |
Output is correct |
21 |
Correct |
31 ms |
9044 KB |
Output is correct |
22 |
Correct |
30 ms |
8276 KB |
Output is correct |
23 |
Correct |
29 ms |
8532 KB |
Output is correct |
24 |
Correct |
30 ms |
8276 KB |
Output is correct |
25 |
Correct |
32 ms |
8952 KB |
Output is correct |
26 |
Correct |
28 ms |
8788 KB |
Output is correct |
27 |
Correct |
31 ms |
8528 KB |
Output is correct |
28 |
Correct |
35 ms |
8892 KB |
Output is correct |
29 |
Correct |
6 ms |
5976 KB |
Output is correct |
30 |
Correct |
9 ms |
6488 KB |
Output is correct |
31 |
Correct |
6 ms |
6236 KB |
Output is correct |
32 |
Correct |
6 ms |
6492 KB |
Output is correct |
33 |
Correct |
7 ms |
6488 KB |
Output is correct |
34 |
Correct |
6 ms |
6744 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
29 ms |
8216 KB |
Output is correct |
37 |
Correct |
30 ms |
8764 KB |
Output is correct |
38 |
Correct |
32 ms |
8532 KB |
Output is correct |
39 |
Correct |
35 ms |
8592 KB |
Output is correct |
40 |
Correct |
30 ms |
9184 KB |
Output is correct |
41 |
Correct |
8 ms |
6488 KB |
Output is correct |
42 |
Correct |
36 ms |
8616 KB |
Output is correct |
43 |
Correct |
30 ms |
9044 KB |
Output is correct |
44 |
Correct |
31 ms |
9028 KB |
Output is correct |
45 |
Correct |
28 ms |
8748 KB |
Output is correct |
46 |
Correct |
29 ms |
9288 KB |
Output is correct |
47 |
Correct |
29 ms |
8960 KB |
Output is correct |