# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1042455 | vjudge1 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
vector<long long> at, ac, ca, ct, ta, tc;
void init(string a,string b)
{
int n = a.size() + 1;
a = '#' + a;
b = '#' + b;
at.resize(n + 1, 0);
ac.resize(n + 1, 0);
ca.resize(n + 1, 0);
ct.resize(n + 1, 0);
ta.resize(n + 1, 0);
tc.resize(n + 1, 0);
for(int i = 1; i <= n; ++i)
{
if(a[i] == 'A')
{
if(b[i] == 'C')
ac[i] = ac[i - 1] + 1;
if(b[i] == 'T')
at[i] = at[i - 1] + 1;
}
if(a[i] == 'T')
{
if(b[i] == 'A')
ta[i] = ta[i - 1] + 1;
if(b[i] == 'C')
tc[i] = tc[i - 1] + 1;
}
if(a[i] == 'C')
{
if(b[i] == 'A')
ca[i] = ca[i - 1] + 1;
if(b[i] == 'T')
ct[i] = ct[i - 1] + 1;
}
}
}
int get_distance(int x, int y)
{
int acc = (ac[y + 1] - ac[x]);
int att = (at[y + 1] - at[x]);
int ctt = (ct[y + 1] - ct[x]);
int caa = (ca[y + 1] - ca[x]);
int tcc = (tc[y + 1] - tc[x]);
int taa = (ta[y + 1] - ta[x]);
if(acc + att != taa + caa) {return -1;}
if(caa + ctt != acc + tcc) {return -1;}
if(taa + tcc != att + ctt) {return -1;}
int mn1 = min(acc,caa), mn2 = min(att,taa), mn3 = min(tcc,ctt);
ans += mn1 + mn2 + mn3;
acc -= mn1;
caa -= mn1;
att -= mn2;
taa -= mn2;
tcc -= mn3;
ctt -= mn3;
int sum = max({att, taa, ctt, tcc, acc, caa});
ans += sum * 2;
return ans;
}