#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<map<pair<char, char>, int>> values;
void init(std::string a, std::string b) {
int N = a.size();
values.resize(N + 1);
for(int i = 0; i < N; i++){
char A = a[i]; char B = b[i];
values[i + 1] = values[i];
values[i + 1][{A, B}]++;
}
}
int get_distance(int x, int y) {
// Create difference
map<pair<char, char>, int> last = values[y + 1];
map<pair<char, char>, int> first = values[x]; // might need -2?
map<pair<char, char>, int> difference;
vector<char> conv = {'A', 'C', 'T'};
map<char, int> timesTo;
map<char, int> timesFrom;
for(char c : conv){
for(auto v : conv){
difference[{c, v}] = last[{c, v}] - first[{c, v}];
if(difference[{c, v}] < 0) return -1;
timesTo[v] += difference[{c, v}];
timesFrom[c] += difference[{c, v}];
}
}
if(timesTo.size() != timesFrom.size()) return -1;
for(char c : conv) if(timesTo[c] != timesFrom[c]) return -1;
int amount = 0;
int additional = 0;
for(char c : conv){
for(auto v : conv){
int in = min(difference[{c, v}], difference[{v, c}]);
difference[{c, v}] -= in; difference[{v, c}] -= in;
amount += in;
int remain = max(difference[{c, v}], difference[{v, c}]);
if(remain){
int f = difference[{c, v}];
int b = difference[{v, c}];
additional += remain;
}
difference[{c, v}] = 0; difference[{v, c}] = 0;
}
}
if(additional % 3 != 0) return -1; //is this true?
return amount + (additional / 3) * 2;
}
// #include "grader.cpp"
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |