| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 734503 | Roman70 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
string c,d;
const int sz = 1e5;
int prefix[26][sz];
int prefix1[26][sz];
int prefix2[sz];
void init(std::string a, std::string b) {
c = a;
d = b;
memset(prefix,0,sizeof(prefix));
memset(prefix1,0,sizeof(prefix1));
memset(prefix2,0,sizeof(prefix2));
prefix[0][c[0] - 'A']++;
prefix1[0][d[0] - 'A']++;
// 65 67 84
if(c[0] != d[0]) prefix2[0]++;
for(int i = 1;i<c.size();i++){
prefix[i][c[i] - 'A']++;
prefix[i][0]+= prefix[i-1][0];
prefix[i][2]+= prefix[i-1][2];
prefix[i][19]+= prefix[i-1][19];
if(c[i] != d[i]) prefix2[i]++;
prefix2[i] += prefix2[i-1];
}
for(int i = 1;i<d.size();i++){
prefix1[i][d[i] - 'A']++;
prefix1[i][0]+= prefix1[i-1][0];
prefix1[i][2]+= prefix1[i-1][2];
prefix1[i][19]+= prefix1[i-1][19];
}
}
int get_distance(int x, int y) {
int ans;
int cmp[2][26];
cmp[0][0] = prefix[y][0] - (x == 0 ? 0 : prefix[x-1][0]);
cmp[0][2]= prefix[y][2] - (x == 0 ? 0 : prefix[x-1][2]);
cmp[0][19]= prefix[y][19] - (x == 0 ? 0 : prefix[x-1][19]);
cmp[1][0]= prefix1[y][0] - (x == 0 ? 0 : prefix1[x-1][0]);
cmp[1][2]= prefix1[y][2] - (x == 0 ? 0 : prefix1[x-1][2]);
cmp[1][19]= prefix1[y][19] - (x == 0 ? 0 : prefix1[x-1][19]);
if(cmp[0][0] == cmp[1][0] && cmp[0][2] == cmp[1][2] && cmp[0][19] == cmp[1][19]) return (prefix2[y] - (x == 0 ? 0 : prefix2[x-1])) / 2 + ((prefix2[y] - (x == 0 ? 0 : prefix2[x-1])) % 2);
return -1;
}
int main(){
init("ATACAT", "ACTATA");
cout<<get_distance(3,5);
return 0;
}