# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1270798 | cmiuc | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include "dna.h"
using namespace std;
const int M = 1<<17;
int TA[M], AT[M], CA[M], AC[M], TC[M], CT[M];
void init(string a, string b){
int n = a.size();
a = '0' + a;
b = '0' + b;
for (int i=1;i<=n;i++){
TA[i] = TA[i-1] + (a[i] == 'T' and b[i] == 'A');
AT[i] = AT[i-1] + (a[i] == 'A' and b[i] == 'T');
CA[i] = CA[i-1] + (a[i] == 'C' and b[i] == 'A');
AC[i] = AC[i-1] + (a[i] == 'A' and b[i] == 'C');
TC[i] = TC[i-1] + (a[i] == 'T' and b[i] == 'C');
CT[i] = CT[i-1] + (a[i] == 'C' and b[i] == 'T');
}
}
int get_distance(int l, int r, int ans = 0){
int ta = TA[r+1] - TA[l];
int at = AT[r+1] - AT[l];
int k = min(ta, at);
ta -= k, at -= k, ans += k;
int ca = CA[r+1] - CA[l];
int ac = AC[r+1] - AC[l];
k = min(ca, ac);
ca -= k, ac -= k, ans += k;
int ct = CT[r+1] - CT[l];
int tc = TC[r+1] - TC[l];
k = min(tc, ct);
tc -= k, ct -= k, ans += k;
if (ta == ac and ac == ct and at == tc and tc == ca)
return ta * 2 + at * 2 + ans;
return -1;
}