| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1142047 | rayank | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string A;
string B;
void init(string a, string b) {
A = a;
B = b;
}
int find_pos(int k, vector<int> nums){
for(int i = 0; i < nums.size(); i++){
if(nums[i] == k){
return i;
}
}
return -1;
}
vector<int> string_to_int(string s){
map<char, int> nums;
vector<int> res;
nums['A'] = 0;
nums['C'] = 1;
nums['T'] = -1;
for(int i = 0; i < s.size(); i++){
res.push_back(nums[s[i]]);
}
return res;
}
int get_distance(int x, int y) {
vector<int> a = string_to_int(A.substr(x,y));
vector<int> b = string_to_int(B.substr(x,y));
if(accumulate(a.begin(), a.end(), 0) != accumulate(b.begin(), b.end(), 0)){
return -1;
}
int res = 0;
int i = 0;
while(a!=b){
if(i >= a.size()){
i = 0;
}
if(a[i] == b[i]){
i++;
continue;
}
swap(a[i], a[find_pos(a[i], b)]);
res++;
i++;
}
return res;
}
int main() {
int n,q;
cin>>n>>q;
string a,b;
cin>>a>>b;
init(a,b);
while(q--){
int x,y;
cin>>x>>y;
cout<<get_distance(x,y)<<endl;
}
}