| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 840824 | Jkap | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll>
#define for1(i, n) for (ll i=0; i<n; i++)
int nA1[100005], nA2[100005], nC1[100005], nC2[100005], AT[100005], AC[100005], CT[100005], CA[100005], TC[100005], TA[100005];
void init(string a, string b) {
ll n = a.size();
for1(i, n) {
nA1[i+1] = nA1[i];
nC1[i+1] = nC1[i];
nA2[i+1] = nA2[i];
nC2[i+1] = nC2[i];
AT[i+1] = AT[i];
AC[i+1] = AC[i];
CT[i+1] = CT[i];
CA[i+1] = CA[i];
TA[i+1] = TA[i];
TC[i+1] = TC[i];
if (a[i] == 'A') {
nA1[i+1]++;
if (b[i] == 'C') {
AC[i+1] ++;
}
if (b[i] == 'T') {
AT[i+1] ++;
}
}
else if (a[i] == 'C') {
nC1[i+1] ++;
if (b[i] == 'A') {
CA[i+1] ++;
}
if (b[i] == 'T') {
CT[i+1] ++;
}
}
else {
if (b[i] == 'C') {
TC[i+1] ++;
}
if (b[i] == 'A') {
TA[i+1] ++;
}
}
if (b[i] == 'A') {
nA2[i+1]++;
}
else if (b[i] == 'C') {
nC2[i+1] ++;
}
}
}
int get_distance(int x, int y) {
if (nA1[y+1] - nA1[x] != nA2[y+1] - nA2[x] || nC1[y+1] - nC1[x] != nC2[y+1] - nC2[x]) {
return -1;
}
int out;
out = min(AC[y+1]-AC[x], CA[y+1]-CA[x]);
out += min(AT[y+1]-AT[x], TA[y+1]-TA[x]);
out += min(TC[y+1]-TC[x], CT[y+1]-CT[x]);
out += 2*(max(AC[y+1]-AC[x], CA[y+1]-CA[x]) - min(AC[y+1]-AC[x], CA[y+1]-CA[x]));
return out;
}
int main() {
int q;
cin >> q;
string a, b;
cin >> a >> b;
init(a, b);
for1(i, q) {
int x, y;
cin >> x >> y;
cout << get_distance(x, y) << endl;
}
}