#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
map<char,int> translator;
vector<vector<vector<int> > > operations;
vector<vector<int> > cnt[2];
void init(string a, string b) {
//get n
int n = a.length();
//set size - 1-based index for 0 base case
operations.resize(n+1);
cnt[0].resize(n+1);
cnt[1].resize(n+1);
//set translator
translator['A'] = 0;
translator['T'] = 1;
translator['C'] = 2;
//set base cases
cnt[0][0] = { 0, 0, 0 };
cnt[1][0] = { 0, 0, 0 };
operations[0] = { {0,0,0}, {0,0,0}, {0,0,0} };
//set values
for( int i = 0; i < n; i++ ){
//copy previous values -- count
cnt[0][i+1].resize(3);
cnt[1][i+1].resize(3);
for( int j = 0; j < 3; j++ ){
cnt[0][i+1][j] = cnt[0][i][j];
cnt[1][i+1][j] = cnt[1][i][j];
}
//set new values -- count
cnt[0][i+1][ translator[a[i]] ]++;
cnt[1][i+1][ translator[b[i]] ]++;
//copy previous values -- operations
operations[i+1].resize(3);
for( int j = 0; j < 3; j++ ){
operations[i+1][j].resize(3);
for( int k = 0; k < 3; k++ ){ operations[i+1][j][k] = operations[i][j][k]; }
}
//set new values -- operations
operations[i+1][ translator[a[i]] ][ translator[b[i]] ]++;
}
return;
}
bool possible( int x, int y ){
int valsA, valsB;
for( int i = 0; i < 3; i++ ){
valsA = cnt[0][y][i] - cnt[0][x-1][i];
valsB = cnt[1][y][i] - cnt[1][x-1][i];
if( valsA != valsB ){ return false; }
}
return true;
}
int solve( int x, int y ){
int grand = 0;
vector<vector<int> > use;
use.resize(3);
for( int i = 0; i < 3; i++ ){
use[i].resize(3);
for( int j = 0; j < 3; j++ ){ use[i][j] = operations[y][i][j] - operations[x-1][i][j]; }
}
int mn = min( use[0][1], use[1][0] );
grand += mn;
use[0][1] -= mn; use[1][0] -= mn;
mn = min( use[0][2], use[2][0] );
grand += mn;
use[0][2] -= mn; use[2][0] -= mn;
mn = min( use[1][2], use[2][1] );
grand += mn;
use[1][2] -= mn; use[2][1] -= mn;
int ttl = use[0][1] + use[1][0] + use[0][2] + use[2][0] + use[1][2] + use[2][1];
ttl /= 3;
ttl *= 2;
grand += ttl;
return grand;
}
int get_distance(int x, int y) {
//account for 1-based indexing
x++; y++;
//check if possible
if( !possible(x,y) ){ return -1; }
//return ans
return solve(x,y);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
33604 KB |
Output is correct |
2 |
Correct |
188 ms |
34028 KB |
Output is correct |
3 |
Correct |
189 ms |
31228 KB |
Output is correct |
4 |
Correct |
204 ms |
34036 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 |
75 ms |
31204 KB |
Output is correct |
5 |
Correct |
66 ms |
31568 KB |
Output is correct |
6 |
Correct |
85 ms |
31300 KB |
Output is correct |
7 |
Correct |
66 ms |
29392 KB |
Output is correct |
8 |
Correct |
74 ms |
31540 KB |
Output is correct |
9 |
Correct |
63 ms |
31584 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 |
75 ms |
31204 KB |
Output is correct |
5 |
Correct |
66 ms |
31568 KB |
Output is correct |
6 |
Correct |
85 ms |
31300 KB |
Output is correct |
7 |
Correct |
66 ms |
29392 KB |
Output is correct |
8 |
Correct |
74 ms |
31540 KB |
Output is correct |
9 |
Correct |
63 ms |
31584 KB |
Output is correct |
10 |
Correct |
214 ms |
33652 KB |
Output is correct |
11 |
Correct |
159 ms |
34116 KB |
Output is correct |
12 |
Correct |
163 ms |
32248 KB |
Output is correct |
13 |
Correct |
182 ms |
33032 KB |
Output is correct |
14 |
Correct |
165 ms |
34372 KB |
Output is correct |
15 |
Correct |
166 ms |
34292 KB |
Output is correct |
16 |
Correct |
169 ms |
32176 KB |
Output is correct |
17 |
Correct |
155 ms |
32976 KB |
Output is correct |
18 |
Correct |
169 ms |
34440 KB |
Output is correct |
19 |
Correct |
120 ms |
32176 KB |
Output is correct |
20 |
Correct |
118 ms |
33016 KB |
Output is correct |
21 |
Correct |
123 ms |
34480 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 |
75 ms |
31204 KB |
Output is correct |
5 |
Correct |
66 ms |
31568 KB |
Output is correct |
6 |
Correct |
85 ms |
31300 KB |
Output is correct |
7 |
Correct |
66 ms |
29392 KB |
Output is correct |
8 |
Correct |
74 ms |
31540 KB |
Output is correct |
9 |
Correct |
63 ms |
31584 KB |
Output is correct |
10 |
Correct |
70 ms |
28808 KB |
Output is correct |
11 |
Correct |
80 ms |
31600 KB |
Output is correct |
12 |
Correct |
62 ms |
29508 KB |
Output is correct |
13 |
Correct |
62 ms |
31352 KB |
Output is correct |
14 |
Correct |
67 ms |
31556 KB |
Output is correct |
15 |
Correct |
65 ms |
31584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
33604 KB |
Output is correct |
2 |
Correct |
188 ms |
34028 KB |
Output is correct |
3 |
Correct |
189 ms |
31228 KB |
Output is correct |
4 |
Correct |
204 ms |
34036 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 |
75 ms |
31204 KB |
Output is correct |
12 |
Correct |
66 ms |
31568 KB |
Output is correct |
13 |
Correct |
85 ms |
31300 KB |
Output is correct |
14 |
Correct |
66 ms |
29392 KB |
Output is correct |
15 |
Correct |
74 ms |
31540 KB |
Output is correct |
16 |
Correct |
63 ms |
31584 KB |
Output is correct |
17 |
Correct |
214 ms |
33652 KB |
Output is correct |
18 |
Correct |
159 ms |
34116 KB |
Output is correct |
19 |
Correct |
163 ms |
32248 KB |
Output is correct |
20 |
Correct |
182 ms |
33032 KB |
Output is correct |
21 |
Correct |
165 ms |
34372 KB |
Output is correct |
22 |
Correct |
166 ms |
34292 KB |
Output is correct |
23 |
Correct |
169 ms |
32176 KB |
Output is correct |
24 |
Correct |
155 ms |
32976 KB |
Output is correct |
25 |
Correct |
169 ms |
34440 KB |
Output is correct |
26 |
Correct |
120 ms |
32176 KB |
Output is correct |
27 |
Correct |
118 ms |
33016 KB |
Output is correct |
28 |
Correct |
123 ms |
34480 KB |
Output is correct |
29 |
Correct |
70 ms |
28808 KB |
Output is correct |
30 |
Correct |
80 ms |
31600 KB |
Output is correct |
31 |
Correct |
62 ms |
29508 KB |
Output is correct |
32 |
Correct |
62 ms |
31352 KB |
Output is correct |
33 |
Correct |
67 ms |
31556 KB |
Output is correct |
34 |
Correct |
65 ms |
31584 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
179 ms |
31280 KB |
Output is correct |
37 |
Correct |
145 ms |
34116 KB |
Output is correct |
38 |
Correct |
178 ms |
32480 KB |
Output is correct |
39 |
Correct |
171 ms |
34508 KB |
Output is correct |
40 |
Correct |
162 ms |
34528 KB |
Output is correct |
41 |
Correct |
63 ms |
31556 KB |
Output is correct |
42 |
Correct |
140 ms |
32376 KB |
Output is correct |
43 |
Correct |
149 ms |
34404 KB |
Output is correct |
44 |
Correct |
153 ms |
34344 KB |
Output is correct |
45 |
Correct |
114 ms |
32416 KB |
Output is correct |
46 |
Correct |
121 ms |
34372 KB |
Output is correct |
47 |
Correct |
118 ms |
34324 KB |
Output is correct |