#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
using namespace std;
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long
const int MXN = 1e5 + 5, INF = 1e9 + 5;
map<pair<char, char>, int> cnt[MXN];
map<char, int> char_cnt[MXN];
void init(string a, string b) {
int n = sz(a);
for (int i = 0; i < n; i++) {
cnt[i][make_pair(a[i], b[i])]++;
cnt[i + 1] = cnt[i];
char_cnt[i][a[i]]++;
char_cnt[i][b[i]]--;
char_cnt[i + 1] = char_cnt[i];
}
}
int get_distance(int x, int y) {
if (char_cnt[y]['A'] - (x > 0 ? char_cnt[x - 1]['A'] : 0) != 0) return -1;
if (char_cnt[y]['T'] - (x > 0 ? char_cnt[x - 1]['T'] : 0) != 0) return -1;
if (char_cnt[y]['C'] - (x > 0 ? char_cnt[x - 1]['C'] : 0) != 0) return -1;
int AT = cnt[y][make_pair('A', 'T')] - (x > 0 ? cnt[x - 1][make_pair('A', 'T')] : 0);
int TA = cnt[y][make_pair('T', 'A')] - (x > 0 ? cnt[x - 1][make_pair('T', 'A')] : 0);
int AC = cnt[y][make_pair('A', 'C')] - (x > 0 ? cnt[x - 1][make_pair('A', 'C')] : 0);
int CA = cnt[y][make_pair('C', 'A')] - (x > 0 ? cnt[x - 1][make_pair('C', 'A')] : 0);
int TC = cnt[y][make_pair('T', 'C')] - (x > 0 ? cnt[x - 1][make_pair('T', 'C')] : 0);
int CT = cnt[y][make_pair('C', 'T')] - (x > 0 ? cnt[x - 1][make_pair('C', 'T')] : 0);
int ans = min(AT, TA) + min(AC, CA) + min(TC, CT);
int first = max(AT, TA) - min(AT, TA);
int second = max(AC, CA) - min(CA, AC);
int third = max(TC, CT) - min(TC, CT);
ans += 2 * (first + second + third) / 3;
return ans;
}
// void solve() {
// init("ATC", "TCA");
// cout << get_distance(0, 2) << "\n";
// }
// signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int TC = 1;
// // cin >> TC;
// while (TC--) solve();
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
57796 KB |
Output is correct |
2 |
Correct |
239 ms |
58364 KB |
Output is correct |
3 |
Correct |
265 ms |
64224 KB |
Output is correct |
4 |
Correct |
268 ms |
69272 KB |
Output is correct |
5 |
Correct |
8 ms |
9676 KB |
Output is correct |
6 |
Correct |
8 ms |
9676 KB |
Output is correct |
7 |
Correct |
8 ms |
9592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
58 ms |
38220 KB |
Output is correct |
5 |
Correct |
122 ms |
38596 KB |
Output is correct |
6 |
Correct |
151 ms |
38336 KB |
Output is correct |
7 |
Correct |
56 ms |
36656 KB |
Output is correct |
8 |
Correct |
109 ms |
38692 KB |
Output is correct |
9 |
Correct |
79 ms |
38596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
58 ms |
38220 KB |
Output is correct |
5 |
Correct |
122 ms |
38596 KB |
Output is correct |
6 |
Correct |
151 ms |
38336 KB |
Output is correct |
7 |
Correct |
56 ms |
36656 KB |
Output is correct |
8 |
Correct |
109 ms |
38692 KB |
Output is correct |
9 |
Correct |
79 ms |
38596 KB |
Output is correct |
10 |
Correct |
244 ms |
57788 KB |
Output is correct |
11 |
Correct |
253 ms |
58340 KB |
Output is correct |
12 |
Correct |
251 ms |
57028 KB |
Output is correct |
13 |
Correct |
258 ms |
58052 KB |
Output is correct |
14 |
Correct |
246 ms |
59852 KB |
Output is correct |
15 |
Correct |
283 ms |
60356 KB |
Output is correct |
16 |
Correct |
224 ms |
52008 KB |
Output is correct |
17 |
Correct |
228 ms |
53068 KB |
Output is correct |
18 |
Correct |
266 ms |
54724 KB |
Output is correct |
19 |
Correct |
97 ms |
31856 KB |
Output is correct |
20 |
Correct |
104 ms |
32372 KB |
Output is correct |
21 |
Correct |
134 ms |
33404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
58 ms |
38220 KB |
Output is correct |
5 |
Correct |
122 ms |
38596 KB |
Output is correct |
6 |
Correct |
151 ms |
38336 KB |
Output is correct |
7 |
Correct |
56 ms |
36656 KB |
Output is correct |
8 |
Correct |
109 ms |
38692 KB |
Output is correct |
9 |
Correct |
79 ms |
38596 KB |
Output is correct |
10 |
Correct |
115 ms |
61724 KB |
Output is correct |
11 |
Correct |
128 ms |
66812 KB |
Output is correct |
12 |
Correct |
147 ms |
62916 KB |
Output is correct |
13 |
Correct |
145 ms |
66360 KB |
Output is correct |
14 |
Correct |
136 ms |
66720 KB |
Output is correct |
15 |
Correct |
136 ms |
66776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
57796 KB |
Output is correct |
2 |
Correct |
239 ms |
58364 KB |
Output is correct |
3 |
Correct |
265 ms |
64224 KB |
Output is correct |
4 |
Correct |
268 ms |
69272 KB |
Output is correct |
5 |
Correct |
8 ms |
9676 KB |
Output is correct |
6 |
Correct |
8 ms |
9676 KB |
Output is correct |
7 |
Correct |
8 ms |
9592 KB |
Output is correct |
8 |
Correct |
7 ms |
9676 KB |
Output is correct |
9 |
Correct |
6 ms |
9676 KB |
Output is correct |
10 |
Correct |
7 ms |
9676 KB |
Output is correct |
11 |
Correct |
58 ms |
38220 KB |
Output is correct |
12 |
Correct |
122 ms |
38596 KB |
Output is correct |
13 |
Correct |
151 ms |
38336 KB |
Output is correct |
14 |
Correct |
56 ms |
36656 KB |
Output is correct |
15 |
Correct |
109 ms |
38692 KB |
Output is correct |
16 |
Correct |
79 ms |
38596 KB |
Output is correct |
17 |
Correct |
244 ms |
57788 KB |
Output is correct |
18 |
Correct |
253 ms |
58340 KB |
Output is correct |
19 |
Correct |
251 ms |
57028 KB |
Output is correct |
20 |
Correct |
258 ms |
58052 KB |
Output is correct |
21 |
Correct |
246 ms |
59852 KB |
Output is correct |
22 |
Correct |
283 ms |
60356 KB |
Output is correct |
23 |
Correct |
224 ms |
52008 KB |
Output is correct |
24 |
Correct |
228 ms |
53068 KB |
Output is correct |
25 |
Correct |
266 ms |
54724 KB |
Output is correct |
26 |
Correct |
97 ms |
31856 KB |
Output is correct |
27 |
Correct |
104 ms |
32372 KB |
Output is correct |
28 |
Correct |
134 ms |
33404 KB |
Output is correct |
29 |
Correct |
115 ms |
61724 KB |
Output is correct |
30 |
Correct |
128 ms |
66812 KB |
Output is correct |
31 |
Correct |
147 ms |
62916 KB |
Output is correct |
32 |
Correct |
145 ms |
66360 KB |
Output is correct |
33 |
Correct |
136 ms |
66720 KB |
Output is correct |
34 |
Correct |
136 ms |
66776 KB |
Output is correct |
35 |
Correct |
6 ms |
9676 KB |
Output is correct |
36 |
Correct |
224 ms |
64268 KB |
Output is correct |
37 |
Correct |
255 ms |
69268 KB |
Output is correct |
38 |
Correct |
243 ms |
66212 KB |
Output is correct |
39 |
Correct |
259 ms |
69684 KB |
Output is correct |
40 |
Correct |
317 ms |
69668 KB |
Output is correct |
41 |
Correct |
131 ms |
66648 KB |
Output is correct |
42 |
Correct |
249 ms |
66084 KB |
Output is correct |
43 |
Correct |
245 ms |
69572 KB |
Output is correct |
44 |
Correct |
259 ms |
69568 KB |
Output is correct |
45 |
Correct |
134 ms |
40280 KB |
Output is correct |
46 |
Correct |
116 ms |
42180 KB |
Output is correct |
47 |
Correct |
109 ms |
42136 KB |
Output is correct |