#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#include "dna.h"
map<char, int> charToInt;
vector<vector<vi>> prefCnt;
int n;
void init(std::string a, std::string b) {
charToInt['A'] = 0;
charToInt['C'] = 1;
charToInt['T'] = 2;
n = sz(a);
prefCnt.resize(3, vector<vi>(3, vi(n+1)));
rep(i,0,n) {
rep(x,0,3) rep(y,0,3) prefCnt[x][y][i+1] = prefCnt[x][y][i];
prefCnt[charToInt[a[i]]][charToInt[b[i]]][i+1]++;
}
}
vi operator+(vi a, vi b) {
vi retvalue(3);
rep(i,0,3) retvalue[i] = a[i] + b[i];
return retvalue;
}
void print(vi a) {
trav(elem, a) cerr << elem << ", ";
cerr << endl;
}
int get_distance(int x, int y) {
vector<vi> swapsNeeded(3, vi(3));
rep(a,0,3) rep(b,0,3) {
swapsNeeded[a][b] = prefCnt[a][b][y+1] - prefCnt[a][b][x];
}
rep(i,0,3) {
int in = 0;
int out = 0;
rep(j,0,3) {
in += swapsNeeded[j][i];
out += swapsNeeded[i][j];
}
if (in != out) return -1;
}
int ans = 0;
rep(a,0,3) rep(b,a+1,3) {
int temp = min(swapsNeeded[a][b], swapsNeeded[b][a]);
ans += temp;
swapsNeeded[a][b] -= temp;
swapsNeeded[b][a] -= temp;
}
vector<pii> order({pii(0, 1), pii(0, 2), pii(1, 2)});
//cerr << "ans = " << ans << endl;
//cerr << "swapsNeeded = " << endl;
//trav(v, swapsNeeded)
// print(v);
//cerr << endl;
int bestCost = 1<<30;
rep(_,0,3) {
int tempCost = 0;
vector<vi> currSwapsNeeded = swapsNeeded;
for(auto [a,b] : order) {
//cerr << "swapping " << a << ", " << b << endl;
int temp = min(currSwapsNeeded[a][b], currSwapsNeeded[b][a]);
tempCost += temp;
currSwapsNeeded[a][b] -= temp;
currSwapsNeeded[b][a] -= temp;
if (currSwapsNeeded[a][b] == 0 && currSwapsNeeded[b][a] == 0) continue;
if (currSwapsNeeded[a][b] == 0) swap(a, b);
temp = currSwapsNeeded[a][b];
int c = 3 - a - b;
currSwapsNeeded[a][b] = 0;
currSwapsNeeded[b][c] -= temp;
currSwapsNeeded[a][c] += temp;
tempCost += temp;
//cerr << tempCost << endl;
//trav(v, currSwapsNeeded)
// print(v);
}
bestCost = min(bestCost, tempCost);
next_permutation(all(order));
}
return ans + bestCost;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
7748 KB |
Output is correct |
2 |
Correct |
114 ms |
7872 KB |
Output is correct |
3 |
Correct |
131 ms |
7424 KB |
Output is correct |
4 |
Correct |
112 ms |
7908 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 |
12 ms |
6092 KB |
Output is correct |
5 |
Correct |
12 ms |
6092 KB |
Output is correct |
6 |
Correct |
12 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
5732 KB |
Output is correct |
8 |
Correct |
14 ms |
6092 KB |
Output is correct |
9 |
Correct |
11 ms |
6168 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 |
12 ms |
6092 KB |
Output is correct |
5 |
Correct |
12 ms |
6092 KB |
Output is correct |
6 |
Correct |
12 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
5732 KB |
Output is correct |
8 |
Correct |
14 ms |
6092 KB |
Output is correct |
9 |
Correct |
11 ms |
6168 KB |
Output is correct |
10 |
Correct |
138 ms |
7748 KB |
Output is correct |
11 |
Correct |
134 ms |
7860 KB |
Output is correct |
12 |
Correct |
110 ms |
7464 KB |
Output is correct |
13 |
Correct |
112 ms |
7628 KB |
Output is correct |
14 |
Correct |
117 ms |
7880 KB |
Output is correct |
15 |
Correct |
118 ms |
7876 KB |
Output is correct |
16 |
Correct |
115 ms |
7428 KB |
Output is correct |
17 |
Correct |
144 ms |
7724 KB |
Output is correct |
18 |
Correct |
112 ms |
7880 KB |
Output is correct |
19 |
Correct |
100 ms |
7500 KB |
Output is correct |
20 |
Correct |
100 ms |
7584 KB |
Output is correct |
21 |
Correct |
106 ms |
7876 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 |
12 ms |
6092 KB |
Output is correct |
5 |
Correct |
12 ms |
6092 KB |
Output is correct |
6 |
Correct |
12 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
5732 KB |
Output is correct |
8 |
Correct |
14 ms |
6092 KB |
Output is correct |
9 |
Correct |
11 ms |
6168 KB |
Output is correct |
10 |
Correct |
11 ms |
5604 KB |
Output is correct |
11 |
Correct |
13 ms |
6092 KB |
Output is correct |
12 |
Correct |
12 ms |
5708 KB |
Output is correct |
13 |
Correct |
14 ms |
6080 KB |
Output is correct |
14 |
Correct |
13 ms |
6092 KB |
Output is correct |
15 |
Correct |
12 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
7748 KB |
Output is correct |
2 |
Correct |
114 ms |
7872 KB |
Output is correct |
3 |
Correct |
131 ms |
7424 KB |
Output is correct |
4 |
Correct |
112 ms |
7908 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 |
12 ms |
6092 KB |
Output is correct |
12 |
Correct |
12 ms |
6092 KB |
Output is correct |
13 |
Correct |
12 ms |
6092 KB |
Output is correct |
14 |
Correct |
10 ms |
5732 KB |
Output is correct |
15 |
Correct |
14 ms |
6092 KB |
Output is correct |
16 |
Correct |
11 ms |
6168 KB |
Output is correct |
17 |
Correct |
138 ms |
7748 KB |
Output is correct |
18 |
Correct |
134 ms |
7860 KB |
Output is correct |
19 |
Correct |
110 ms |
7464 KB |
Output is correct |
20 |
Correct |
112 ms |
7628 KB |
Output is correct |
21 |
Correct |
117 ms |
7880 KB |
Output is correct |
22 |
Correct |
118 ms |
7876 KB |
Output is correct |
23 |
Correct |
115 ms |
7428 KB |
Output is correct |
24 |
Correct |
144 ms |
7724 KB |
Output is correct |
25 |
Correct |
112 ms |
7880 KB |
Output is correct |
26 |
Correct |
100 ms |
7500 KB |
Output is correct |
27 |
Correct |
100 ms |
7584 KB |
Output is correct |
28 |
Correct |
106 ms |
7876 KB |
Output is correct |
29 |
Correct |
11 ms |
5604 KB |
Output is correct |
30 |
Correct |
13 ms |
6092 KB |
Output is correct |
31 |
Correct |
12 ms |
5708 KB |
Output is correct |
32 |
Correct |
14 ms |
6080 KB |
Output is correct |
33 |
Correct |
13 ms |
6092 KB |
Output is correct |
34 |
Correct |
12 ms |
6092 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
108 ms |
7428 KB |
Output is correct |
37 |
Correct |
117 ms |
7876 KB |
Output is correct |
38 |
Correct |
116 ms |
7500 KB |
Output is correct |
39 |
Correct |
113 ms |
7872 KB |
Output is correct |
40 |
Correct |
115 ms |
8004 KB |
Output is correct |
41 |
Correct |
11 ms |
6092 KB |
Output is correct |
42 |
Correct |
142 ms |
7464 KB |
Output is correct |
43 |
Correct |
110 ms |
7872 KB |
Output is correct |
44 |
Correct |
110 ms |
7864 KB |
Output is correct |
45 |
Correct |
106 ms |
7496 KB |
Output is correct |
46 |
Correct |
104 ms |
7864 KB |
Output is correct |
47 |
Correct |
106 ms |
7884 KB |
Output is correct |