| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1137152 | Shadow1 | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include "dna_ioi.h"
using namespace std;
#include <bits/stdc++.h>
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define sz(x) int(x.size())
const int maxn = 1e5 + 5;
vector<int> ta(maxn), aa(maxn), cA(maxn), tb(maxn), ab(maxn), cB(maxn), diff(maxn);
vector<int> ct(maxn), ca(maxn), tc(maxn), ac(maxn), cc(maxn);
void init(std::string a, std::string b) {
int n = sz(a);
ta[0] = (a[0] == 'T');
tb[0] = (b[0] == 'T');
aa[0] = (a[0] == 'A');
ab[0] = (b[0] == 'A');
cA[0] = (a[0] == 'C');
cB[0] = (b[0] == 'C');
ct[0] = (a[0] == 'C' && b[0] == 'T');
ca[0] = (a[0] == 'C' && b[0] == 'A');
tc[0] = (a[0] == 'T' && b[0] == 'C');
ac[0] = (a[0] == 'A' && b[0] == 'C');
cc[0] = (a[0] == 'C' && b[0] == 'C');
diff[0] = (b[0] != 'C' && a[0] != b[0]);
for(int i=1; i<n; ++i) {
ta[i] = ta[i-1] + (a[i] == 'T');
tb[i] = tb[i-1] + (b[i] == 'T');
aa[i] = aa[i-1] + (a[i] == 'A');
ab[i] = ab[i-1] + (b[i] == 'A');
cA[i] = cA[i-1] + (a[i] == 'C');
cB[i] = cB[i-1] + (b[i] == 'C');
ct[i] = ct[i-1] + (a[i] == 'C' && b[i] == 'T');
ca[i] = ca[i-1] + (a[i] == 'C' && b[i] == 'A');
tc[i] = tc[i-1] + (a[i] == 'T' && b[i] == 'C');
ac[i] = ac[i-1] + (a[i] == 'A' && b[i] == 'C');
cc[i] = cc[i-1] + (a[i] == 'C' && b[i] == 'C');
diff[i] = diff[i-1];
if(b[i] == 'C') continue;
diff[i] += (a[i] != b[i]);
}
}
int get_distance(int x, int y) {
if(x == 0) {
if(ta[y] != tb[y] || aa[y] != ab[y] || cA[y] != cB[y])
return -1;
else {
int d = diff[y];
d -= min(ct[y], tc[y]);
d -= min(ca[y], ac[y]);
d >>= 1;
return d + (cA[y] - cc[y]);
}
} else {
if(ta[y] - ta[x-1] != tb[y] - tb[x-1] || aa[y] - aa[x-1] != ab[y] - ab[x-1] || cA[y] - cA[x-1] != cB[y] - cB[x-1])
return -1;
else {
int d = diff[y] - diff[x-1];
d -= min(ct[y] - ct[x-1], tc[y] - tc[x-1]);
d -= min(ca[y] - ca[x-1], ac[y] - ac[x-1]);
d >>= 1;
return d + (cA[y] - cA[x-1] - (cc[y] - cc[x-1]));
}
}
}