| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 542256 | apocryphal44 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<string>
//#include<iostream>
using namespace std;
string s_a, s_b;
class DNA{
public:
string str_{};
int A_count{0}, T_count{0}, C_count{0};
DNA (string a) : str_(a) {
for (auto i: str_){
switch((int)i){
case 65:
this->A_count++;
break;
case 67:
this->C_count++;
break;
case 84:
this->T_count++;
break;
default:
throw;
}}}
};
void init(string a, string b){
s_a = a;
s_b = b;
}
int get_distance(int x, int y){
// Validity Check
if (x>y) throw;
if (x<0 or y <0) throw;
// Feasible Check
const int len{y-x+1};
DNA a_sub{s_a.substr((long long unsigned int)x, (long long unsigned int)len)};
DNA b_sub{s_b.substr((long long unsigned int)x, (long long unsigned int)len)};
if ((a_sub.A_count != b_sub.A_count) or (a_sub.C_count != b_sub.C_count) or (a_sub.T_count != b_sub.T_count)) return -1;
// Greedy Algorithm
int r{0}, i{0};
for( auto j : a_sub.str_){
char b_i = b_sub.str_.at((long long unsigned int)i);
if (b_i != j)
{
for (int k{i+1}; k<len; k++){
if (b_sub.str_.at((long long unsigned int)k) == j)
{
b_sub.str_[(long long unsigned int)i] = j;
b_sub.str_[(long long unsigned int)k] = b_i;
r++;
break;
}
}
}
i++;
}
return r;
}
int main(){
int n,q;
string a,b;
cin >> n >>q;
cin >> a;
cin >> b;
init(a,b);
int x,y;
while(q){
cin >> x >> y;
get_distance(x,y);
q--;
}
}
/*
int main(){
string str1, str2;
int a,b;
cin >> str1 >> str2;
init(str1, str2);
cin >> a >> b;
cout << get_distance(a,b);
return 0;
}*/