# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
499136 | LucaIlie | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#define MAX_N 100000
using namespace std;
struct abc {
int ab, ac, ba, bc, ca, cb;
} sp[MAX_N + 1];
void init( string a, string b ) {
int i;
for ( i = 0; i < a.size(); i++ ) {
sp[i + 1].ab = sp[i].ab + (a[i] == 'A' && b[i] == 'T');
sp[i + 1].ac = sp[i].ac + (a[i] == 'A' && b[i] == 'C');
sp[i + 1].ba = sp[i].ba + (a[i] == 'T' && b[i] == 'A');
sp[i + 1].bc = sp[i].bc + (a[i] == 'T' && b[i] == 'C');
sp[i + 1].ca = sp[i].ca + (a[i] == 'C' && b[i] == 'A');
sp[i + 1].cb = sp[i].cb + (a[i] == 'C' && b[i] == 'T');
}
}
int get_distance( int x, int y ) {
int ab, ac, ba, bc, ca, cb;
y++;
ab = sp[y].ab - sp[x].ab;
ac = sp[y].ac - sp[x].ac;
ba = sp[y].ba - sp[x].ba;
bc = sp[y].bc - sp[x].bc;
ca = sp[y].ca - sp[x].ca;
cb = sp[y].cb - sp[x].cb;
if ( ab + ac == ba + ca && ba + bc == ab + cb && ca + cb == ac + bc ) {
int cost, x;
cost = min( ab, ba ) + min( ac, ca ) + min( bc, cb );
ab = abs( ab - ba );
bc = abs( bc - cb );
ca = abs( ac - ca );
ba = cb = ac = 0;
x = min( ab, bc );
cost += x;
ab -= x;
bc -= x;
ac += x;
x = min( ac, ca );
cost += x;
ac -= x;
ca -= x;
return cost;
}
return -1;
}
int main() {
int x, y;
string a, b;
cin >> a >> b;
init( a, b );
while ( 1 ) {
cin >> x >> y;
cout << get_distance( x, y ) << "\n";
}
return 0;
}