| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1341240 | Almonther | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<dna.h>
#define ll long long
#define co cout<<
using namespace std;
// stuff
const int maxn=1e5+5;
ll pref[maxn][6],c[maxn][2];
map<string,ll>mp;
void init(string a, string b){
mp["AT"]=0;
mp["TA"]=5;
mp["AC"]=1;
mp["CA"]=4;
mp["CT"]=2;
mp["TC"]=3;
for(int i=1;i<=a.size();i++){
for(int j=0;j<6;j++) pref[i][j]=pref[i-1][j];
c[i][0]=c[i-1][0];
c[i][1]=c[i-1][1];
if(a[i-1]=='A') c[i][0]++;
if(b[i-1]=='A') c[i][0]--;
if(a[i-1]=='C') c[i][1]++;
if(b[i-1]=='C') c[i][1]--;
if(a[i-1]==b[i-1]) continue;
string t="";
t+=a[i-1];
t+=b[i-1];
pref[i][mp[t]]++;
}
}
int get_distance(int x, int y){
if(c[y][0]-c[x-1][0]!=0||c[y][1]-c[x-1][1]!=0) return -1;
ll arr[6];
for(int i=0;i<6;i++) arr[i]=pref[y][i];
for(int i=0;i<6;i++) arr[i]-=pref[x-1][i];
ll ans=0;
for(int i=0;i<3;i++){
ll x=min(arr[i],arr[5-i]);
ans+=x;
arr[i]-=x;
arr[5-i]-=x;
}
ll sum=0;
for(int i=0;i<6;i++) sum+=arr[i];
return ans+sum-sum/3;
}
// void solve(){
// }
// int main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// int _=1;
// // cin>>_;
// while(_--) solve();
// }