#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define dbg(x) cout << #x << " " << x << endl;
#define ll long long
#define ld long double
// template<typename T>
// void pr(vector<T>& a) {
// for(auto i: a) {
// cout << i << " ";
// }
// cout << endl;
// }
void pr(vector<pair<int, int>>& a) {
for(auto i: a) {
cout << "{" << i.first << "," << i.second << "}" << " ";
}
cout << endl;
}
void pr(vector<pair<pair<int, int>, int>>& a) {
for(auto i: a) {
cout << "{ {" << i.first.first << "," << i.first.second << "}" << ", " << i.second << "} ";
}
cout << endl;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int N = 2e5 + 10;
int p1[N][3], p2[N][3];
int ac[N], ca[N];
int at[N], ta[N];
int ct[N], tc[N];
int n;
void init(std::string a, std::string b) {
n = sz(a);
map<pair<char, char>, int> mp;
for(int i = 0; i < n; i++) {
p1[i + 1][0] += p1[i][0] + (a[i] == 'A');
p1[i + 1][1] += p1[i][1] + (a[i] == 'T');
p1[i + 1][2] += p1[i][2] + (a[i] == 'C');
p2[i + 1][0] += p2[i][0] + (b[i] == 'A');
p2[i + 1][1] += p2[i][1] + (b[i] == 'T');
p2[i + 1][2] += p2[i][2] + (b[i] == 'C');
ac[i + 1] = ac[i];
ca[i + 1] = ca[i];
at[i + 1] = at[i];
ta[i + 1] = ta[i];
ct[i + 1] = ct[i];
tc[i + 1] = tc[i];
if(a[i] == 'A' && b[i] == 'C') {
ac[i + 1]++;
}
if(a[i] == 'A' && b[i] == 'T') {
at[i + 1]++;
}
if(a[i] == 'C' && b[i] == 'T') {
ct[i + 1]++;
}
if(a[i] == 'C' && b[i] == 'A') {
ca[i + 1]++;
}
if(a[i] == 'T' && b[i] == 'A') {
ta[i + 1]++;
}
if(a[i] == 'T' && b[i] == 'C') {
tc[i + 1]++;
}
}
}
int get_distance(int x, int y) {
x++, y++;
swap(x, y);
int a1 = p1[x][0] - p1[y - 1][0];
int t1 = p1[x][1] - p1[y - 1][1];
int c1 = p1[x][2] - p1[y - 1][2];
int a2 = p2[x][0] - p2[y - 1][0];
int t2 = p2[x][1] - p2[y - 1][1];
int c2 = p2[x][2] - p2[y - 1][2];
if(a1 != a2 || t1 != t2 || c1 != c2) {
return -1;
}
int answ = 0;
int tta = ta[x] - ta[y - 1];
int aat = at[x] - at[y - 1];
int mini = min(tta, aat);
tta -= mini, aat -= mini;
answ += mini;
int ttc = tc[x] - tc[y - 1];
int cct = ct[x] - ct[y - 1];
mini = min(ttc, cct);
answ += mini;
cct -= mini, ttc -= mini;
int aac = ac[x] - ac[y - 1];
int cca = ca[x] - ca[y - 1];
mini = min(aac, cca);
answ += mini;
cca -= mini, aac -= mini;
int all_sum = aat + tta + ttc + cct + aac + cca;
assert(all_sum % 3 == 0);
return answ + 2 * (all_sum / 3);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
6796 KB |
Output is correct |
2 |
Correct |
34 ms |
6920 KB |
Output is correct |
3 |
Correct |
33 ms |
6396 KB |
Output is correct |
4 |
Correct |
32 ms |
6920 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
5 ms |
5460 KB |
Output is correct |
5 |
Correct |
6 ms |
5588 KB |
Output is correct |
6 |
Correct |
6 ms |
5576 KB |
Output is correct |
7 |
Correct |
6 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
5 ms |
5460 KB |
Output is correct |
5 |
Correct |
6 ms |
5588 KB |
Output is correct |
6 |
Correct |
6 ms |
5576 KB |
Output is correct |
7 |
Correct |
6 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5588 KB |
Output is correct |
10 |
Correct |
35 ms |
6772 KB |
Output is correct |
11 |
Correct |
33 ms |
6904 KB |
Output is correct |
12 |
Correct |
31 ms |
6868 KB |
Output is correct |
13 |
Correct |
33 ms |
7040 KB |
Output is correct |
14 |
Correct |
32 ms |
7224 KB |
Output is correct |
15 |
Correct |
29 ms |
7192 KB |
Output is correct |
16 |
Correct |
28 ms |
6812 KB |
Output is correct |
17 |
Correct |
30 ms |
7048 KB |
Output is correct |
18 |
Correct |
38 ms |
7284 KB |
Output is correct |
19 |
Correct |
45 ms |
6904 KB |
Output is correct |
20 |
Correct |
29 ms |
7068 KB |
Output is correct |
21 |
Correct |
29 ms |
7304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
5 ms |
5460 KB |
Output is correct |
5 |
Correct |
6 ms |
5588 KB |
Output is correct |
6 |
Correct |
6 ms |
5576 KB |
Output is correct |
7 |
Correct |
6 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5716 KB |
Output is correct |
9 |
Correct |
4 ms |
5588 KB |
Output is correct |
10 |
Correct |
5 ms |
5076 KB |
Output is correct |
11 |
Correct |
5 ms |
5588 KB |
Output is correct |
12 |
Correct |
5 ms |
5204 KB |
Output is correct |
13 |
Correct |
6 ms |
5524 KB |
Output is correct |
14 |
Correct |
5 ms |
5588 KB |
Output is correct |
15 |
Correct |
5 ms |
5588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
6796 KB |
Output is correct |
2 |
Correct |
34 ms |
6920 KB |
Output is correct |
3 |
Correct |
33 ms |
6396 KB |
Output is correct |
4 |
Correct |
32 ms |
6920 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 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 |
5 ms |
5460 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
6 ms |
5576 KB |
Output is correct |
14 |
Correct |
6 ms |
5204 KB |
Output is correct |
15 |
Correct |
5 ms |
5716 KB |
Output is correct |
16 |
Correct |
4 ms |
5588 KB |
Output is correct |
17 |
Correct |
35 ms |
6772 KB |
Output is correct |
18 |
Correct |
33 ms |
6904 KB |
Output is correct |
19 |
Correct |
31 ms |
6868 KB |
Output is correct |
20 |
Correct |
33 ms |
7040 KB |
Output is correct |
21 |
Correct |
32 ms |
7224 KB |
Output is correct |
22 |
Correct |
29 ms |
7192 KB |
Output is correct |
23 |
Correct |
28 ms |
6812 KB |
Output is correct |
24 |
Correct |
30 ms |
7048 KB |
Output is correct |
25 |
Correct |
38 ms |
7284 KB |
Output is correct |
26 |
Correct |
45 ms |
6904 KB |
Output is correct |
27 |
Correct |
29 ms |
7068 KB |
Output is correct |
28 |
Correct |
29 ms |
7304 KB |
Output is correct |
29 |
Correct |
5 ms |
5076 KB |
Output is correct |
30 |
Correct |
5 ms |
5588 KB |
Output is correct |
31 |
Correct |
5 ms |
5204 KB |
Output is correct |
32 |
Correct |
6 ms |
5524 KB |
Output is correct |
33 |
Correct |
5 ms |
5588 KB |
Output is correct |
34 |
Correct |
5 ms |
5588 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
43 ms |
6392 KB |
Output is correct |
37 |
Correct |
35 ms |
6912 KB |
Output is correct |
38 |
Correct |
44 ms |
6916 KB |
Output is correct |
39 |
Correct |
35 ms |
7192 KB |
Output is correct |
40 |
Correct |
32 ms |
7296 KB |
Output is correct |
41 |
Correct |
5 ms |
5588 KB |
Output is correct |
42 |
Correct |
39 ms |
6896 KB |
Output is correct |
43 |
Correct |
43 ms |
7180 KB |
Output is correct |
44 |
Correct |
30 ms |
7256 KB |
Output is correct |
45 |
Correct |
33 ms |
6908 KB |
Output is correct |
46 |
Correct |
31 ms |
7232 KB |
Output is correct |
47 |
Correct |
33 ms |
7284 KB |
Output is correct |