| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 691660 | vjudge1 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define vl vector<ll>
#define endl "\n"
#define INF 0x3F3F3F3F
using namespace std;
const int sz=1e5+5;
vl pew(sz),pac(sz),pat(sz),paa(sz),pba(sz),pbc(sz),pbt(sz);
ll n,q;
int get_distance(ll l, ll r){
ll cntac=pac[r]-pac[l-1];
ll cntbc=pbc[r]-pbc[l-1];
ll cntaa=paa[r]-paa[l-1];
ll cntba=pba[r]-pba[l-1];
ll cntat=pat[r]-pat[l-1];
ll cntbt=pbt[r]-pbt[l-1];
if(cntaa!=cntba or cntac!=cntbc or cntat!=cntbt){
return -1;
}
ll res=pew[r]-pew[l-1];
int ans=res/2+(res%2);
return ans;
}
void init(string a, string b){
if(a[0]!=b[0]){pew[0]=0;}
if(a[0]=='A'){paa[0]=1;}
else if(a[0]=='C'){pac[0]=1;}
else{pat[0]=1;}
if(b[0]=='A'){pba[0]=1;}
else if(b[0]=='C'){pbc[0]=1;}
else{pbt[0]=1;}
for(ll i=1;i<n;i++){
if(a[i]!=b[i]){pew[i]=pew[i-1]+1;}
else{pew[i]=pew[i-1];}
if(a[i]=='A'){paa[i]=paa[i-1]+1;}
else if(a[i]=='C'){pac[i]=pac[i-1]+1;}
else{pat[i]=pat[i-1]+1;}
if(b[i]=='A'){pba[i]=pba[i-1]+1;}
else if(b[i]=='C'){pbc[i]=pbc[i-1]+1;}
else{pbt[i]=pbt[i-1]+1;}
pat[i]=max(pat[i],pat[i-1]);
pac[i]=max(pac[i],pac[i-1]);
paa[i]=max(paa[i],paa[i-1]);
pbt[i]=max(pbt[i],pbt[i-1]);
pbc[i]=max(pbc[i],pbc[i-1]);
pba[i]=max(pba[i],pba[i-1]);
}
return ;
}
/*
*/