| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1141956 | rayank | 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(char c, string s, int start, int end){
for(int i = start; i <= end; i++){
if(s[i] == c){
return i;
}
}
return -1;
}
bool issamee(string a, string b, int start, int end){
for(int i = start; i <= end; i++){
if(a[i] != b[i]){
return false;
}
}
return true;
}
int get_distance(int x, int y) {
int res = 0;
string suba = A.substr(x, y);
string subb = B.substr(x,y);
string acopy = A;
sort(suba.begin(), suba.end());
sort(subb.begin(), subb.end());
if(suba != subb){
return -1;
}
for(int i=x; i <=y;i++){
if(acopy[i] == B[i]) continue;
int pos = find_pos(acopy[i], B, x, y);
if(pos == -1) return -1;
swap(acopy[i], acopy[pos]);
res++;
}
if(!issamee(acopy, B, x, y)) return -1;
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;
}
}