#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
struct Psum {
vector<int> p;
Psum() : p {} {}
Psum(const vector<int>& arr) : p(sz(arr) + 1) {
partial_sum(begin(arr), end(arr), p.begin() + 1);
}
int query(int l, int r) const {
return p[r + 1] - p[l];
}
} arr[3][3];
const string conv = "ACT";
void init(string a, string b) {
int n = sz(a);
vector<int> cnts[3][3];
for (auto& a : cnts) {
for (auto& b : a) {
b.resize(n);
}
}
for (int i = 0; i < n; i++) {
cnts[conv.find(a[i])][conv.find(b[i])][i]++;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
arr[i][j] = Psum(cnts[i][j]);
}
}
}
int get_distance(int l, int r) {
int cnt[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cnt[i][j] = arr[i][j].query(l, r);
}
}
int ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i != j) {
int x = min(cnt[i][j], cnt[j][i]);
ans += x;
cnt[i][j] -= x;
cnt[j][i] -= x;
}
}
}
for (int i : {1, 2}) {
int j = 1 ^ 2 ^ i;
int &a = cnt[0][i], &b = cnt[i][j], &c = cnt[j][0];
int x = min({a, b, c});
a -= x;
b -= x;
c -= x;
ans += 2 * x;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i != j && cnt[i][j]) {
return -1;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
10316 KB |
Output is correct |
2 |
Correct |
39 ms |
10424 KB |
Output is correct |
3 |
Correct |
37 ms |
9780 KB |
Output is correct |
4 |
Correct |
42 ms |
10416 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
8020 KB |
Output is correct |
5 |
Correct |
6 ms |
8116 KB |
Output is correct |
6 |
Correct |
7 ms |
7996 KB |
Output is correct |
7 |
Correct |
7 ms |
7508 KB |
Output is correct |
8 |
Correct |
7 ms |
8116 KB |
Output is correct |
9 |
Correct |
7 ms |
8116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
8020 KB |
Output is correct |
5 |
Correct |
6 ms |
8116 KB |
Output is correct |
6 |
Correct |
7 ms |
7996 KB |
Output is correct |
7 |
Correct |
7 ms |
7508 KB |
Output is correct |
8 |
Correct |
7 ms |
8116 KB |
Output is correct |
9 |
Correct |
7 ms |
8116 KB |
Output is correct |
10 |
Correct |
49 ms |
10316 KB |
Output is correct |
11 |
Correct |
41 ms |
10424 KB |
Output is correct |
12 |
Correct |
42 ms |
9788 KB |
Output is correct |
13 |
Correct |
41 ms |
10024 KB |
Output is correct |
14 |
Correct |
40 ms |
10448 KB |
Output is correct |
15 |
Correct |
44 ms |
10420 KB |
Output is correct |
16 |
Correct |
36 ms |
9736 KB |
Output is correct |
17 |
Correct |
38 ms |
10032 KB |
Output is correct |
18 |
Correct |
36 ms |
10292 KB |
Output is correct |
19 |
Correct |
33 ms |
9772 KB |
Output is correct |
20 |
Correct |
35 ms |
9984 KB |
Output is correct |
21 |
Correct |
33 ms |
10300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
8020 KB |
Output is correct |
5 |
Correct |
6 ms |
8116 KB |
Output is correct |
6 |
Correct |
7 ms |
7996 KB |
Output is correct |
7 |
Correct |
7 ms |
7508 KB |
Output is correct |
8 |
Correct |
7 ms |
8116 KB |
Output is correct |
9 |
Correct |
7 ms |
8116 KB |
Output is correct |
10 |
Correct |
5 ms |
7476 KB |
Output is correct |
11 |
Correct |
6 ms |
8148 KB |
Output is correct |
12 |
Correct |
6 ms |
7612 KB |
Output is correct |
13 |
Correct |
7 ms |
8048 KB |
Output is correct |
14 |
Correct |
7 ms |
8148 KB |
Output is correct |
15 |
Correct |
8 ms |
8148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
10316 KB |
Output is correct |
2 |
Correct |
39 ms |
10424 KB |
Output is correct |
3 |
Correct |
37 ms |
9780 KB |
Output is correct |
4 |
Correct |
42 ms |
10416 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
6 ms |
8020 KB |
Output is correct |
12 |
Correct |
6 ms |
8116 KB |
Output is correct |
13 |
Correct |
7 ms |
7996 KB |
Output is correct |
14 |
Correct |
7 ms |
7508 KB |
Output is correct |
15 |
Correct |
7 ms |
8116 KB |
Output is correct |
16 |
Correct |
7 ms |
8116 KB |
Output is correct |
17 |
Correct |
49 ms |
10316 KB |
Output is correct |
18 |
Correct |
41 ms |
10424 KB |
Output is correct |
19 |
Correct |
42 ms |
9788 KB |
Output is correct |
20 |
Correct |
41 ms |
10024 KB |
Output is correct |
21 |
Correct |
40 ms |
10448 KB |
Output is correct |
22 |
Correct |
44 ms |
10420 KB |
Output is correct |
23 |
Correct |
36 ms |
9736 KB |
Output is correct |
24 |
Correct |
38 ms |
10032 KB |
Output is correct |
25 |
Correct |
36 ms |
10292 KB |
Output is correct |
26 |
Correct |
33 ms |
9772 KB |
Output is correct |
27 |
Correct |
35 ms |
9984 KB |
Output is correct |
28 |
Correct |
33 ms |
10300 KB |
Output is correct |
29 |
Correct |
5 ms |
7476 KB |
Output is correct |
30 |
Correct |
6 ms |
8148 KB |
Output is correct |
31 |
Correct |
6 ms |
7612 KB |
Output is correct |
32 |
Correct |
7 ms |
8048 KB |
Output is correct |
33 |
Correct |
7 ms |
8148 KB |
Output is correct |
34 |
Correct |
8 ms |
8148 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
44 ms |
9744 KB |
Output is correct |
37 |
Correct |
37 ms |
10456 KB |
Output is correct |
38 |
Correct |
39 ms |
9888 KB |
Output is correct |
39 |
Correct |
55 ms |
10432 KB |
Output is correct |
40 |
Correct |
44 ms |
10360 KB |
Output is correct |
41 |
Correct |
7 ms |
8152 KB |
Output is correct |
42 |
Correct |
38 ms |
9804 KB |
Output is correct |
43 |
Correct |
35 ms |
10324 KB |
Output is correct |
44 |
Correct |
37 ms |
10256 KB |
Output is correct |
45 |
Correct |
49 ms |
9804 KB |
Output is correct |
46 |
Correct |
36 ms |
10324 KB |
Output is correct |
47 |
Correct |
34 ms |
10316 KB |
Output is correct |