// #include<iostream>
#include "dna.h"
using namespace std;
const int mxN = 1e5+5;
int qs_a[mxN][3];
int qs_b[mxN][3];
int pp[mxN][3][3];
bool can(int x, int y) {
if((qs_a[y][0] - qs_a[x-1][0]) != (qs_b[y][0] - qs_b[x-1][0])) return false;
if((qs_a[y][1] - qs_a[x-1][1]) != (qs_b[y][1] - qs_b[x-1][1])) return false;
if((qs_a[y][2] - qs_a[x-1][2]) != (qs_b[y][2] - qs_b[x-1][2])) return false;
return true;
}
int parse(char c) {
if(c == 'A') return 0;
if(c == 'C') return 1;
return 2;
}
void reset(int i) {
for(int j = 0; j < 3; ++j) {
qs_a[i][j] = qs_a[i-1][j];
qs_b[i][j] = qs_b[i-1][j];
}
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) {
pp[i][j][k] = pp[i-1][j][k];
}
}
return;
}
void init(string a, string b) {
int n = a.size();
for(int i = 1; i <= n; ++i) {
reset(i);
if(parse(a[i-1]) == parse(b[i-1])) continue;
qs_a[i][parse(a[i-1])] = qs_a[i-1][parse(a[i-1])] + 1;
qs_b[i][parse(b[i-1])] = qs_b[i-1][parse(b[i-1])] + 1;
pp[i][parse(a[i-1])][parse(b[i-1])] = pp[i-1][parse(a[i-1])][parse(b[i-1])] + 1;
// cout << pp[i][parse(a[i-1])][parse(b[i-1])] << ' ' << parse(a[i-1]) << ' ' << parse(b[i-1]) << '\n';
}
}
int get_distance(int x, int y) {
++x, ++y;
if(!can(x,y)) {
return -1;
}
int cnt = 0;
for(int i = 0; i < 3; ++i) {
cnt += qs_a[y][i] - qs_a[x-1][i];
}
int cnt_pair = 0;
for(int i = 0; i < 3; ++i) {
for(int j = i+1; j < 3; ++j) {
int p1 = pp[y][i][j] - pp[x-1][i][j];
int p2 = pp[y][j][i] - pp[x-1][j][i];
if(p1 > 0 && p2 > 0){ // มีคู่ตรงข้ามกัน
cnt_pair += min(p1, p2);
cnt -= min(p1, p2) * 2;
}
}
}
// cout << pp[0][1];
// return cnt_pair;
return cnt_pair + (cnt/3)*2;
// return (all - cnt_pair) % 3 * 2;
}
# | 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... |