| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 483704 | tredsused70 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
using namespace std;
#define accelerator ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax=200011,mod=1000000007,inf=2000010000,key=200003;
const ll infll=4000000000000000000;
const ld eps=1e-7;
void init()
{
return ;
}
string a,b;
int cntc[nmax][3]={0},mas1[nmax]={0},mas2[nmax]={0},cnt[nmax][3][3]={0};
void cnv(string &s,int mas[])
{
int n=s.size();
for(int i=0;i<n;i++)
{
if(s[i]=='A')
{
mas[i+1]=0;
continue;
}
if(s[i]=='T')
mas[i+1]=1;
else
mas[i+1]=2;
}
return ;
}
void init(string &a,string &b)
{
cnv(a,mas1);
cnv(b,mas2);
int n=a.size();
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
cntc[i+1][j]=cntc[i][j];
cntc[i+1][mas1[i+1]]++;
cntc[i+1][mas2[i+1]]--;
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
cnt[i+1][j][k]=cnt[i][j][k];
cnt[i+1][mas1[i+1]][mas2[i+1]]++;
}
return ;
}
int count_swaps(int mas[3][3])
{
int ans=0,t;
for(int i=0;i<3;i++)
{
mas[i][i]=0;
for(int j=i+1;j<3;j++)
{
t=min(mas[i][j],mas[j][i]);
ans+=t;
mas[i][j]-=t;
mas[j][i]-=t;
}
}
t=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
t+=mas[i][j];
ans+=2*t/3;
return ans;
}
int get_distance(int l,int r)
{
r++;
for(int i=0;i<3;i++)
{
if(cntc[l][i]!=cntc[r][i])
return -1;
}
int cntt[3][3];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cntt[i][j]=cnt[r][i][j];
cntt[i][j]-=cnt[l][i][j];
}
return count_swaps(cntt);
}