#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string a, b;
vector<map<pair<char, char>, int>> link;
vector<map<char, int>> dp1, dp2;
void init(std::string A, std::string B) {
a = A;
b = B;
dp1 = vector<map<char, int>>(a.size());
dp2 = vector<map<char, int>>(a.size());
link = vector<map<pair<char, char>, int>>(a.size());
for (int i = 0; i < a.size(); i++) {
if (i > 0) {
dp1[i] = dp1[i-1];
dp2[i] = dp2[i-1];
link[i] = link[i-1];
}
dp1[i][a[i]]++;
dp2[i][b[i]]++;
link[i][{a[i], b[i]}]++;
}
}
int get_distance(int x, int y) {
if (x != 0) {
if (!(
dp1[y]['A']-dp1[x-1]['A'] == dp2[y]['A']-dp2[x-1]['A'] &&
dp1[y]['C']-dp1[x-1]['C'] == dp2[y]['C']-dp2[x-1]['C'] &&
dp1[y]['T']-dp1[x-1]['T'] == dp2[y]['T']-dp2[x-1]['T']
))
return -1;
} else {
if (!(
dp1[y]['A'] == dp2[y]['A'] &&
dp1[y]['C'] == dp2[y]['C'] &&
dp1[y]['T'] == dp2[y]['T']
)) return -1;
}
int AC = link[y][{'A', 'C'}] - (x > 0? link[x-1][{'A', 'C'}] : 0);
int CA = link[y][{'C', 'A'}] - (x > 0? link[x-1][{'C', 'A'}] : 0);
int CT = link[y][{'C', 'T'}] - (x > 0? link[x-1][{'C', 'T'}] : 0);
int TC = link[y][{'T', 'C'}] - (x > 0? link[x-1][{'T', 'C'}] : 0);
int AT = link[y][{'A', 'T'}] - (x > 0? link[x-1][{'A', 'T'}] : 0);
int TA = link[y][{'T', 'A'}] - (x > 0? link[x-1][{'T', 'A'}] : 0);
int res = 0;
res += min(AC, CA)+min(CT, TC)+min(AT, TA);
int tmp = min(AC, CA);
AC -= tmp;
CA -= tmp;
tmp = min(AT, TA);
AT -= tmp;
TA -= tmp;
tmp = min(CT, TC);
CT -= tmp;
TC -= tmp;
if (AC+CA+AT+TA+CT+TC != 0) {
res += 2*(AC+CA+AT+TA+CT+TC)/3;
} else
res += (AC+CA+AT+TA+CT+TC)/2;
return res;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
237 ms |
73828 KB |
Output is correct |
2 |
Correct |
260 ms |
74780 KB |
Output is correct |
3 |
Correct |
226 ms |
79500 KB |
Output is correct |
4 |
Correct |
233 ms |
86872 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
73 ms |
52112 KB |
Output is correct |
5 |
Correct |
77 ms |
52684 KB |
Output is correct |
6 |
Correct |
91 ms |
52288 KB |
Output is correct |
7 |
Correct |
74 ms |
49140 KB |
Output is correct |
8 |
Correct |
85 ms |
52764 KB |
Output is correct |
9 |
Correct |
75 ms |
52812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
73 ms |
52112 KB |
Output is correct |
5 |
Correct |
77 ms |
52684 KB |
Output is correct |
6 |
Correct |
91 ms |
52288 KB |
Output is correct |
7 |
Correct |
74 ms |
49140 KB |
Output is correct |
8 |
Correct |
85 ms |
52764 KB |
Output is correct |
9 |
Correct |
75 ms |
52812 KB |
Output is correct |
10 |
Correct |
262 ms |
73908 KB |
Output is correct |
11 |
Correct |
245 ms |
74748 KB |
Output is correct |
12 |
Correct |
290 ms |
71860 KB |
Output is correct |
13 |
Correct |
290 ms |
73524 KB |
Output is correct |
14 |
Correct |
276 ms |
76552 KB |
Output is correct |
15 |
Correct |
288 ms |
77184 KB |
Output is correct |
16 |
Correct |
246 ms |
66024 KB |
Output is correct |
17 |
Correct |
247 ms |
67636 KB |
Output is correct |
18 |
Correct |
246 ms |
70472 KB |
Output is correct |
19 |
Correct |
107 ms |
43632 KB |
Output is correct |
20 |
Correct |
116 ms |
44736 KB |
Output is correct |
21 |
Correct |
146 ms |
46796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
73 ms |
52112 KB |
Output is correct |
5 |
Correct |
77 ms |
52684 KB |
Output is correct |
6 |
Correct |
91 ms |
52288 KB |
Output is correct |
7 |
Correct |
74 ms |
49140 KB |
Output is correct |
8 |
Correct |
85 ms |
52764 KB |
Output is correct |
9 |
Correct |
75 ms |
52812 KB |
Output is correct |
10 |
Correct |
157 ms |
78044 KB |
Output is correct |
11 |
Correct |
163 ms |
85708 KB |
Output is correct |
12 |
Correct |
176 ms |
80076 KB |
Output is correct |
13 |
Correct |
160 ms |
85256 KB |
Output is correct |
14 |
Correct |
178 ms |
85748 KB |
Output is correct |
15 |
Correct |
166 ms |
85708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
237 ms |
73828 KB |
Output is correct |
2 |
Correct |
260 ms |
74780 KB |
Output is correct |
3 |
Correct |
226 ms |
79500 KB |
Output is correct |
4 |
Correct |
233 ms |
86872 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 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 |
73 ms |
52112 KB |
Output is correct |
12 |
Correct |
77 ms |
52684 KB |
Output is correct |
13 |
Correct |
91 ms |
52288 KB |
Output is correct |
14 |
Correct |
74 ms |
49140 KB |
Output is correct |
15 |
Correct |
85 ms |
52764 KB |
Output is correct |
16 |
Correct |
75 ms |
52812 KB |
Output is correct |
17 |
Correct |
262 ms |
73908 KB |
Output is correct |
18 |
Correct |
245 ms |
74748 KB |
Output is correct |
19 |
Correct |
290 ms |
71860 KB |
Output is correct |
20 |
Correct |
290 ms |
73524 KB |
Output is correct |
21 |
Correct |
276 ms |
76552 KB |
Output is correct |
22 |
Correct |
288 ms |
77184 KB |
Output is correct |
23 |
Correct |
246 ms |
66024 KB |
Output is correct |
24 |
Correct |
247 ms |
67636 KB |
Output is correct |
25 |
Correct |
246 ms |
70472 KB |
Output is correct |
26 |
Correct |
107 ms |
43632 KB |
Output is correct |
27 |
Correct |
116 ms |
44736 KB |
Output is correct |
28 |
Correct |
146 ms |
46796 KB |
Output is correct |
29 |
Correct |
157 ms |
78044 KB |
Output is correct |
30 |
Correct |
163 ms |
85708 KB |
Output is correct |
31 |
Correct |
176 ms |
80076 KB |
Output is correct |
32 |
Correct |
160 ms |
85256 KB |
Output is correct |
33 |
Correct |
178 ms |
85748 KB |
Output is correct |
34 |
Correct |
166 ms |
85708 KB |
Output is correct |
35 |
Correct |
1 ms |
296 KB |
Output is correct |
36 |
Correct |
248 ms |
80788 KB |
Output is correct |
37 |
Correct |
246 ms |
88268 KB |
Output is correct |
38 |
Correct |
250 ms |
83444 KB |
Output is correct |
39 |
Correct |
255 ms |
88636 KB |
Output is correct |
40 |
Correct |
246 ms |
88584 KB |
Output is correct |
41 |
Correct |
163 ms |
85724 KB |
Output is correct |
42 |
Correct |
240 ms |
83468 KB |
Output is correct |
43 |
Correct |
238 ms |
88620 KB |
Output is correct |
44 |
Correct |
254 ms |
88504 KB |
Output is correct |
45 |
Correct |
149 ms |
57676 KB |
Output is correct |
46 |
Correct |
174 ms |
61088 KB |
Output is correct |
47 |
Correct |
163 ms |
61144 KB |
Output is correct |