| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 480689 | Haidara | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define FOR(i,n) rep(i,0,n)
using namespace std;
const int maxn=100200;
int t[2][maxn],a[2][maxn],c[2][maxn],tc[maxn],ct[maxn],at[maxn],ta[maxn],ac[maxn],ca[maxn];
void compute(string s,int inx)
{
int n=s.size();
FOR(i,n)
{
a[inx][i+1]=a[inx][i]+(int)(s[i]=='A');
t[inx][i+1]=t[inx][i]+(int)(s[i]=='T');
c[inx][i+1]=c[inx][i]+(int)(s[i]=='C');
}
}
string s,l;
void init(string x, string y)
{
s=x,l=y;
compute(x,0);
compute(y,1);
FOR(i,n)
{
ta[i+1]=ta[i]+(int)(s[i]=='T'&&l[i]=='A');
at[i+1]=at[i]+(int)(s[i]=='A'&&l[i]=='T');
ac[i+1]=ac[i]+(int)(s[i]=='A'&&l[i]=='C');
ca[i+1]=ca[i]+(int)(s[i]=='C'&&l[i]=='A');
tc[i+1]=tc[i]+(int)(s[i]=='T'&&l[i]=='C');
ct[i+1]=ct[i]+(int)(s[i]=='C'&&l[i]=='T');
}
}
int get_distance(int x,int y)
{
if(t[0][y]-t[0][x-1]!=t[1][y]-t[1][x-1]||
c[0][y]-c[0][x-1]!=c[1][y]-c[1][x-1]||
a[0][y]-a[0][x-1]!=a[1][y]-a[1][x-1])
return -1;
int ans=0;
int TC=tc[y]-tc[x-1];
int CT=ct[y]-ct[x-1];
int AC=ac[y]-ac[x-1];
int CA=ca[y]-ca[x-1];
int TA=ta[y]-ta[x-1];
int AT=at[y]-at[x-1];
int dx;
dx=abs(AT-TA);
ans+=dx;
AT-=dx;
TA-=dx;
dx=abs(AC-CA);
ans+=dx;
AC-=dx;
CA-=dx;
dx=abs(TC-CT);
ans+=dx;
TC-=dx;
CT-=dx;
ans+=((TC+CT+AT+TA+CA+AC)*2)/3;
return ans;
}