| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 676128 | 12332100 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,ss;
ll dna[2][3][100001],jem[100001],res[100001][6];
map<char,ll>mp;
void init(string s,string ss) {
mp['A']=0;
mp['T']=1;
mp['C']=2;
dna[0][mp[s[0]]][0]=1;
dna[1][mp[ss[0]]][0]=1;
for(ll i=1;i<s.size();i++){
if(s[i]==ss[i])jem[i]=jem[i-1]+1;
else jem[i]=jem[i-1];
//
for(ll j=0;j<3;j++){
dna[0][j][i]=dna[0][j][i-1];
dna[1][j][i]=dna[1][j][i-1];
}
dna[0][mp[s[i]]][i]++;
dna[1][mp[ss[i]]][i]++;
//
}
for(ll i=0;i<s.size();i++){
if(i)for(ll j=0;j<6;j++)res[i][j]=res[i-1][j];
if(s[i]=='A'){
if(ss[i]=='T'){
res[i][0]++;
}
else{
res[i][2]++;
}
}else if(s[i]=='T'){
if(ss[i]=='A'){
res[i][1]++;
}else{
res[i][5]++;
}
}else{
if(ss[i]=='A'){
res[i][3]++;
}else{
res[i][4]++;
}
}
}
}
/*
A T 0
T A 1
A C 2
C A 3
C T 4
T C 5
*/
/*
ATATATTATTTAA
TAATTATTATAAA
*/
ll get_distance(ll x, ll y) {
ll cnt=jem[y]-(x-1<0?0:jem[x-1]);
ll a1=dna[0][0][y]-(x-1<0?0:dna[0][0][x-1]);
ll t1=dna[0][1][y]-(x-1<0?0:dna[0][1][x-1]);
ll c1=dna[0][2][y]-(x-1<0?0:dna[0][2][x-1]);
ll a2=dna[1][0][y]-(x-1<0?0:dna[1][0][x-1]);
ll t2=dna[1][1][y]-(x-1<0?0:dna[1][1][x-1]);
ll c2=dna[1][2][y]-(x-1<0?0:dna[1][2][x-1]);
ll len=y-x+1;
if(a1!=a2 || t1!=t2 || c1!=c2)return -1;
ll at=min(res[y][0]-(x-1<0?0:res[x-1][0]),res[y][1]-(x-1<0?0:res[x-1][1]));
ll ac=min(res[y][2]-(x-1<0?0:res[x-1][2]),res[y][3]-(x-1<0?0:res[x-1][3]));
ll tc=min(res[y][4]-(x-1<0?0:res[x-1][4]),res[y][5]-(x-1<0?0:res[x-1][5]));
ll atc=len-(cnt+(at*2)+(ac*2)+(tc*2));
return (at+ac+tc+((2*atc)/3));
}