#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n;
string s, t;
vector<vector<int>> pref1, pref2, inds;
vector<string> pr;
map<string, vector<vector<int>>> mp;
void init(std::string a, std::string b) {
s = a;
t = b;
n = (int) s.length();
pref1 = vector<vector<int>>(n, vector<int>(26));
pref2 = vector<vector<int>>(n, vector<int>(26));
pref1[0][s[0] - 'A']++;
pref2[0][t[0] - 'A']++;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
pref1[i][j] = pref1[i - 1][j];
pref2[i][j] = pref2[i - 1][j];
}
pref1[i][s[i] - 'A']++;
pref2[i][t[i] - 'A']++;
}
auto getPrefix = [&](char c, char d) {
vector<int> pref(n);
if (s[0] == c && t[0] == d) {
pref[0] = 1;
}
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1];
if (s[i] == c && t[i] == d) {
pref[i]++;
}
}
return pref;
};
string str = "ACT";
int m = (int) str.length();
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
string cur;
cur += str[i];
cur += str[j];
vector<int> pref1 = getPrefix(str[i], str[j]);
vector<int> pref2 = getPrefix(str[j], str[i]);
mp[cur].push_back(pref1);
mp[cur].push_back(pref2);
}
}
inds.resize(26);
for (int i = 0; i < n; i++) {
if (s[i] == t[i]) {
inds[s[i] - 'A'].push_back(i);
}
}
}
int get_distance(int x, int y) {
for (int j = 0; j < 26; j++) {
int cnt1 = pref1[y][j] - (x > 0 ? pref1[x - 1][j] : 0);
int cnt2 = pref2[y][j] - (x > 0 ? pref2[x - 1][j] : 0);
if (cnt1 != cnt2) {
return -1;
}
}
int cntA = pref1[y][0] - (x > 0 ? pref1[x - 1][0] : 0);
int len = y - x + 1;
for (int i = 0; i < 26; i++) {
if (inds[i].empty()) {
continue;
}
auto ub = upper_bound(inds[i].begin(), inds[i].end(), y);
auto lb = lower_bound(inds[i].begin(), inds[i].end(), x);
if (ub == inds[i].begin()) {
continue;
}
if (lb == inds[i].end()) {
continue;
}
--ub;
int aa = ub - inds[i].begin();
int bb = lb - inds[i].begin();
swap(aa, bb);
len -= (bb - aa + 1);
if (i == 0) {
cntA -= (bb - aa + 1);
}
}
int res = 0;
for (auto& [str, pref] : mp) {
int cnt1 = pref[0][y] - (x > 0 ? pref[0][x - 1] : 0);
int cnt2 = pref[1][y] - (x > 0 ? pref[1][x - 1] : 0);
int rem = min(cnt1, cnt2);
if (str[0] == 'A') {
cntA -= rem;
}
len -= 2 * rem;
res += rem;
}
res += cntA;
len -= cntA;
return res + len / 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
185 ms |
32340 KB |
Output is correct |
2 |
Correct |
179 ms |
32616 KB |
Output is correct |
3 |
Correct |
184 ms |
30008 KB |
Output is correct |
4 |
Correct |
195 ms |
32692 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
30600 KB |
Output is correct |
5 |
Correct |
41 ms |
30964 KB |
Output is correct |
6 |
Correct |
41 ms |
30752 KB |
Output is correct |
7 |
Correct |
38 ms |
28852 KB |
Output is correct |
8 |
Correct |
40 ms |
30980 KB |
Output is correct |
9 |
Correct |
39 ms |
31264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
30600 KB |
Output is correct |
5 |
Correct |
41 ms |
30964 KB |
Output is correct |
6 |
Correct |
41 ms |
30752 KB |
Output is correct |
7 |
Correct |
38 ms |
28852 KB |
Output is correct |
8 |
Correct |
40 ms |
30980 KB |
Output is correct |
9 |
Correct |
39 ms |
31264 KB |
Output is correct |
10 |
Correct |
173 ms |
32248 KB |
Output is correct |
11 |
Correct |
179 ms |
32616 KB |
Output is correct |
12 |
Correct |
217 ms |
30908 KB |
Output is correct |
13 |
Correct |
175 ms |
32596 KB |
Output is correct |
14 |
Correct |
179 ms |
33872 KB |
Output is correct |
15 |
Correct |
178 ms |
34060 KB |
Output is correct |
16 |
Correct |
156 ms |
31612 KB |
Output is correct |
17 |
Correct |
191 ms |
32340 KB |
Output is correct |
18 |
Correct |
169 ms |
33688 KB |
Output is correct |
19 |
Correct |
82 ms |
31716 KB |
Output is correct |
20 |
Correct |
84 ms |
32424 KB |
Output is correct |
21 |
Correct |
86 ms |
33716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
30600 KB |
Output is correct |
5 |
Correct |
41 ms |
30964 KB |
Output is correct |
6 |
Correct |
41 ms |
30752 KB |
Output is correct |
7 |
Correct |
38 ms |
28852 KB |
Output is correct |
8 |
Correct |
40 ms |
30980 KB |
Output is correct |
9 |
Correct |
39 ms |
31264 KB |
Output is correct |
10 |
Correct |
39 ms |
28192 KB |
Output is correct |
11 |
Correct |
40 ms |
30940 KB |
Output is correct |
12 |
Correct |
39 ms |
28908 KB |
Output is correct |
13 |
Correct |
40 ms |
30780 KB |
Output is correct |
14 |
Correct |
49 ms |
30996 KB |
Output is correct |
15 |
Correct |
39 ms |
30916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
185 ms |
32340 KB |
Output is correct |
2 |
Correct |
179 ms |
32616 KB |
Output is correct |
3 |
Correct |
184 ms |
30008 KB |
Output is correct |
4 |
Correct |
195 ms |
32692 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
39 ms |
30600 KB |
Output is correct |
12 |
Correct |
41 ms |
30964 KB |
Output is correct |
13 |
Correct |
41 ms |
30752 KB |
Output is correct |
14 |
Correct |
38 ms |
28852 KB |
Output is correct |
15 |
Correct |
40 ms |
30980 KB |
Output is correct |
16 |
Correct |
39 ms |
31264 KB |
Output is correct |
17 |
Correct |
173 ms |
32248 KB |
Output is correct |
18 |
Correct |
179 ms |
32616 KB |
Output is correct |
19 |
Correct |
217 ms |
30908 KB |
Output is correct |
20 |
Correct |
175 ms |
32596 KB |
Output is correct |
21 |
Correct |
179 ms |
33872 KB |
Output is correct |
22 |
Correct |
178 ms |
34060 KB |
Output is correct |
23 |
Correct |
156 ms |
31612 KB |
Output is correct |
24 |
Correct |
191 ms |
32340 KB |
Output is correct |
25 |
Correct |
169 ms |
33688 KB |
Output is correct |
26 |
Correct |
82 ms |
31716 KB |
Output is correct |
27 |
Correct |
84 ms |
32424 KB |
Output is correct |
28 |
Correct |
86 ms |
33716 KB |
Output is correct |
29 |
Correct |
39 ms |
28192 KB |
Output is correct |
30 |
Correct |
40 ms |
30940 KB |
Output is correct |
31 |
Correct |
39 ms |
28908 KB |
Output is correct |
32 |
Correct |
40 ms |
30780 KB |
Output is correct |
33 |
Correct |
49 ms |
30996 KB |
Output is correct |
34 |
Correct |
39 ms |
30916 KB |
Output is correct |
35 |
Correct |
1 ms |
288 KB |
Output is correct |
36 |
Correct |
168 ms |
30752 KB |
Output is correct |
37 |
Correct |
198 ms |
33460 KB |
Output is correct |
38 |
Correct |
204 ms |
31996 KB |
Output is correct |
39 |
Correct |
205 ms |
33808 KB |
Output is correct |
40 |
Correct |
192 ms |
33840 KB |
Output is correct |
41 |
Correct |
39 ms |
31284 KB |
Output is correct |
42 |
Correct |
175 ms |
31848 KB |
Output is correct |
43 |
Correct |
184 ms |
33756 KB |
Output is correct |
44 |
Correct |
179 ms |
33816 KB |
Output is correct |
45 |
Correct |
87 ms |
31884 KB |
Output is correct |
46 |
Correct |
104 ms |
33740 KB |
Output is correct |
47 |
Correct |
84 ms |
33788 KB |
Output is correct |