#include <bits/stdc++.h>
#define MAX 105000
#include "dna.h"
int ps[3][2][MAX];
int dest[3][3][MAX];
void prefix_sum(int* arr,int n){
int count = 0;
for(int i=0;i!=n;++i){
count+=*arr;
*arr=count;
++arr;
}
}
int get_segment(int*arr,int l,int r) {
--l;
int res = 0;
if(l>=0)res-=arr[l];
res+=arr[r];
return res;
}
void init(std::string a,std::string b){
std::vector<int> v1,v2;
for(auto&x:a){
if(x=='A')v1.push_back(0);
else if(x=='T')v1.push_back(1);
else v1.push_back(2);
}
for(auto&x:b){
if(x=='A')v2.push_back(0);
else if(x=='T')v2.push_back(1);
else v2.push_back(2);
}
for(int i=0;i!=v1.size();++i){
ps[v1[i]][0][i]++;
ps[v2[i]][1][i]++;
if(v1[i]!=v2[i]){
dest[v1[i]][v2[i]][i]++;
}
}
for(int i=0;i!=3;++i){
prefix_sum(&ps[i][0][0],MAX-3);
prefix_sum(&ps[i][1][0],MAX-3);
}
for(int i=0;i!=3;++i){
for(int j=0;j!=3;++j){
prefix_sum(&dest[i][j][0],MAX-3);
}
}
}
int get_distance(int x,int y){
for(int i=0;i!=3;++i){
if(get_segment(&ps[i][0][0],x,y)!=get_segment(&ps[i][1][0],x,y)){
return -1;
}
}
int tabela[3][3];
for(int i=0;i!=3;++i){
for(int j=0;j!=3;++j){
tabela[i][j]=get_segment(&dest[i][j][0],x,y);
}
}
int custo = 0;
for(int i=0;i!=3;++i){
for(int j=0;j!=3;++j){
int min = std::min(tabela[i][j],tabela[j][i]);
custo+=min;
tabela[i][j]-=min;
tabela[j][i]-=min;
}
}
for(int __=0;__!=5;++__)
for(int i=0;i!=3;++i){
for(int j=0;j!=3;++j){
for(int k=0;k!=3;++k){
int min = std::min(tabela[i][j],std::min(tabela[j][k],tabela[k][i]));
custo+=min*2;
tabela[i][j]-=min;
tabela[j][k]-=min;
tabela[k][i]-=min;
}
}
}
return custo;
}
Compilation message
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i!=v1.size();++i){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
138 ms |
10428 KB |
Output is correct |
2 |
Correct |
144 ms |
10416 KB |
Output is correct |
3 |
Correct |
139 ms |
10300 KB |
Output is correct |
4 |
Correct |
129 ms |
10416 KB |
Output is correct |
5 |
Correct |
5 ms |
6348 KB |
Output is correct |
6 |
Correct |
6 ms |
6348 KB |
Output is correct |
7 |
Correct |
5 ms |
6348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6348 KB |
Output is correct |
2 |
Correct |
5 ms |
6348 KB |
Output is correct |
3 |
Correct |
6 ms |
6348 KB |
Output is correct |
4 |
Correct |
10 ms |
8136 KB |
Output is correct |
5 |
Correct |
10 ms |
8136 KB |
Output is correct |
6 |
Correct |
10 ms |
8132 KB |
Output is correct |
7 |
Correct |
11 ms |
8004 KB |
Output is correct |
8 |
Correct |
10 ms |
8124 KB |
Output is correct |
9 |
Correct |
9 ms |
8108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6348 KB |
Output is correct |
2 |
Correct |
5 ms |
6348 KB |
Output is correct |
3 |
Correct |
6 ms |
6348 KB |
Output is correct |
4 |
Correct |
10 ms |
8136 KB |
Output is correct |
5 |
Correct |
10 ms |
8136 KB |
Output is correct |
6 |
Correct |
10 ms |
8132 KB |
Output is correct |
7 |
Correct |
11 ms |
8004 KB |
Output is correct |
8 |
Correct |
10 ms |
8124 KB |
Output is correct |
9 |
Correct |
9 ms |
8108 KB |
Output is correct |
10 |
Correct |
130 ms |
10404 KB |
Output is correct |
11 |
Correct |
128 ms |
10432 KB |
Output is correct |
12 |
Correct |
132 ms |
10308 KB |
Output is correct |
13 |
Correct |
123 ms |
10356 KB |
Output is correct |
14 |
Correct |
128 ms |
10432 KB |
Output is correct |
15 |
Correct |
136 ms |
10412 KB |
Output is correct |
16 |
Correct |
128 ms |
10160 KB |
Output is correct |
17 |
Correct |
118 ms |
10280 KB |
Output is correct |
18 |
Correct |
117 ms |
10300 KB |
Output is correct |
19 |
Correct |
127 ms |
10120 KB |
Output is correct |
20 |
Correct |
112 ms |
10308 KB |
Output is correct |
21 |
Correct |
115 ms |
10292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6348 KB |
Output is correct |
2 |
Correct |
5 ms |
6348 KB |
Output is correct |
3 |
Correct |
6 ms |
6348 KB |
Output is correct |
4 |
Correct |
10 ms |
8136 KB |
Output is correct |
5 |
Correct |
10 ms |
8136 KB |
Output is correct |
6 |
Correct |
10 ms |
8132 KB |
Output is correct |
7 |
Correct |
11 ms |
8004 KB |
Output is correct |
8 |
Correct |
10 ms |
8124 KB |
Output is correct |
9 |
Correct |
9 ms |
8108 KB |
Output is correct |
10 |
Correct |
9 ms |
8004 KB |
Output is correct |
11 |
Correct |
10 ms |
8152 KB |
Output is correct |
12 |
Correct |
9 ms |
8012 KB |
Output is correct |
13 |
Correct |
10 ms |
8132 KB |
Output is correct |
14 |
Correct |
10 ms |
8136 KB |
Output is correct |
15 |
Correct |
10 ms |
8116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
138 ms |
10428 KB |
Output is correct |
2 |
Correct |
144 ms |
10416 KB |
Output is correct |
3 |
Correct |
139 ms |
10300 KB |
Output is correct |
4 |
Correct |
129 ms |
10416 KB |
Output is correct |
5 |
Correct |
5 ms |
6348 KB |
Output is correct |
6 |
Correct |
6 ms |
6348 KB |
Output is correct |
7 |
Correct |
5 ms |
6348 KB |
Output is correct |
8 |
Correct |
5 ms |
6348 KB |
Output is correct |
9 |
Correct |
5 ms |
6348 KB |
Output is correct |
10 |
Correct |
6 ms |
6348 KB |
Output is correct |
11 |
Correct |
10 ms |
8136 KB |
Output is correct |
12 |
Correct |
10 ms |
8136 KB |
Output is correct |
13 |
Correct |
10 ms |
8132 KB |
Output is correct |
14 |
Correct |
11 ms |
8004 KB |
Output is correct |
15 |
Correct |
10 ms |
8124 KB |
Output is correct |
16 |
Correct |
9 ms |
8108 KB |
Output is correct |
17 |
Correct |
130 ms |
10404 KB |
Output is correct |
18 |
Correct |
128 ms |
10432 KB |
Output is correct |
19 |
Correct |
132 ms |
10308 KB |
Output is correct |
20 |
Correct |
123 ms |
10356 KB |
Output is correct |
21 |
Correct |
128 ms |
10432 KB |
Output is correct |
22 |
Correct |
136 ms |
10412 KB |
Output is correct |
23 |
Correct |
128 ms |
10160 KB |
Output is correct |
24 |
Correct |
118 ms |
10280 KB |
Output is correct |
25 |
Correct |
117 ms |
10300 KB |
Output is correct |
26 |
Correct |
127 ms |
10120 KB |
Output is correct |
27 |
Correct |
112 ms |
10308 KB |
Output is correct |
28 |
Correct |
115 ms |
10292 KB |
Output is correct |
29 |
Correct |
9 ms |
8004 KB |
Output is correct |
30 |
Correct |
10 ms |
8152 KB |
Output is correct |
31 |
Correct |
9 ms |
8012 KB |
Output is correct |
32 |
Correct |
10 ms |
8132 KB |
Output is correct |
33 |
Correct |
10 ms |
8136 KB |
Output is correct |
34 |
Correct |
10 ms |
8116 KB |
Output is correct |
35 |
Correct |
5 ms |
6348 KB |
Output is correct |
36 |
Correct |
128 ms |
10300 KB |
Output is correct |
37 |
Correct |
134 ms |
10396 KB |
Output is correct |
38 |
Correct |
121 ms |
10304 KB |
Output is correct |
39 |
Correct |
135 ms |
10432 KB |
Output is correct |
40 |
Correct |
124 ms |
10352 KB |
Output is correct |
41 |
Correct |
9 ms |
8148 KB |
Output is correct |
42 |
Correct |
116 ms |
10264 KB |
Output is correct |
43 |
Correct |
122 ms |
10284 KB |
Output is correct |
44 |
Correct |
118 ms |
10304 KB |
Output is correct |
45 |
Correct |
115 ms |
10224 KB |
Output is correct |
46 |
Correct |
115 ms |
10304 KB |
Output is correct |
47 |
Correct |
112 ms |
10288 KB |
Output is correct |