#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string a, b;
void my_init(std::string aa, std::string bb) {
a = aa;
b = bb;
}
int my_get_distance(int x, int y) {
int db1=0, db2=0;
for(int i=x; i<=y; i++){
if(a[i] == 'A' && b[i] == 'T') db1++;
else if(a[i] == 'T' && b[i] == 'A') db2++;
}
if(db1 != db2) return -1;
return db1;
}
const int maxn = 1e5 + 5;
int p1[maxn][3];
int p2[maxn][3];
int p3[maxn][3][3];
int s1[maxn];
int s2[maxn];
void init(string a, string b) {
memset(p1, 0, sizeof(p1));
memset(p2, 0, sizeof(p2));
memset(p3, 0, sizeof(p3));
for (int i = 0; i < a.size(); i++) {
if (a[i] == 'A')
s1[i] = 0;
else if (a[i] == 'C')
s1[i] = 1;
else
s1[i] = 2;
if (b[i] == 'A')
s2[i] = 0;
else if (b[i] == 'C')
s2[i] = 1;
else
s2[i] = 2;
}
p1[0][s1[0]]++;
p2[0][s2[0]]++;
p3[0][s1[0]][s2[0]]++;
for (int i = 1; i < a.size(); i++) {
for (int t1 = 0; t1 <= 2; t1++) {
for (int t2 = 0; t2 <= 2; t2++) {
p3[i][t1][t2] = p3[i - 1][t1][t2];
}
p1[i][t1] = p1[i - 1][t1];
p2[i][t1] = p2[i - 1][t1];
}
p3[i][s1[i]][s2[i]]++;
p1[i][s1[i]]++;
p2[i][s2[i]]++;
}
}
int c[3][3];
int get_distance(int x, int y) {
if (x == 0) {
if (p1[y][0] != p2[y][0] || p1[y][1] != p2[y][1] || p1[y][2] != p2[y][2]) {
return -1;
}
} else {
if (p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] ||
p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] ||
p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2]) {
return -1;
}
}
for (int i = 0; i <= 2; i++) {
for (int j = 0; j <= 2; j++) {
if (x == 0)
c[i][j] = p3[y][i][j];
else
c[i][j] = p3[y][i][j] - p3[x - 1][i][j];
}
}
int ans = 0;
int all = y - x + 1;
all -= c[0][0];
all -= c[1][1];
all -= c[2][2];
int h = min(c[0][1], c[1][0]);
ans += h;
all -= 2*h;
h = min(c[0][2], c[2][0]);
ans += h;
all -= 2*h;
h = min(c[1][2], c[2][1]);
ans += h;
all -= 2*h;
ans += (all / 3) * 2;
return ans;
}
/*void stress(){
srand(42);
int n = 7;
string s = "AT";
while(true){
string a, b;
for(int i=0; i<n; i++){
a += s[rand() % 2];
b += s[rand() % 2];
}
init(a, b);
my_init(a, b);
for(int i=0; i<n-1; i++){
for(int j=i; j<n-1; j++){
if(get_distance(i, j) != my_get_distance(i, j)){
cout << n << " 1\n";
cout << a << "\n" << b << "\n" << i << " " << j << endl;
cout << get_distance(i, j) << endl;
return;
}
}
}
}
}
int main(){
stress();
}*/
# | 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... |