| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1332121 | Tesla89 | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dna.h"
#define tesal ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ain(x,n) for(int i=0;i<n;i++)cin>>x[i];
#define fi first
#define se second
#define pii pair<int,int>
#define YNOut(fun) if(fun){cout<<"YES\n";}else{cout<<"NO\n";}
#define deb(arr) {for(auto i:arr){cout<<i<<' ';}cout<<'\n';}
#define int long long
using namespace std;
int n;
vector<vector<int>>suma,sumb;
vector<vector<vector<int>>>cnt;
void reset(){
suma.resize(n+1,vector<int>(3,0));
sumb.resize(n+1,vector<int>(3,0));
cnt.resize(n+1,vector<vector<int>>(3,vector<int>(3,0)));
}
int gtoi(char c){
switch(c){
case 'A':
return 0;
case 'T':
return 1;
case 'C':
return 2;
default:
cerr<<"Unexpected character"<<'\n';
return -1;
}
}
void init(string a, string b) {
n=a.size();
reset();
for(int i=0;i<n;i++){
suma[i+1]=suma[i];
sumb[i+1]=sumb[i];
cnt[i+1]=cnt[i];
suma[i+1][gtoi(a[i])]++;
sumb[i+1][gtoi(b[i])]++;
cnt[i+1][gtoi(a[i])][gtoi(b[i])]++;
}
}
int get_distance(int x, int y) {
x++;y++;
for(int i=0;i<3;i++){
if(suma[y][i]-suma[x-1][i]!=sumb[y][i]-sumb[x-1][i])
return -1;
}
int dist=0;
vector<int>a(3),t(3),c(3);
for(int i=0;i<3;i++){
a[i]=cnt[y][0][i]-cnt[x-1][0][i];
t[i]=cnt[y][1][i]-cnt[x-1][1][i];
c[i]=cnt[y][2][i]-cnt[x-1][2][i];
}
a[0]=0;t[1]=0;c[2]=0;
int at=min(a[1],t[0]),ac=min(a[2],c[0]),tc=min(t[2],c[1]);
dist=at+ac+tc+max(a[1]-at,t[0]-at)*2;
return dist;
}