# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1142156 | ashen_x | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
//cout<<
//cin>>
int swa=0;
vector<int>v;
bool chars(string x, string y){
sort(x.begin(),x.end());
sort(y.begin(),y.end());
if(x!=y){
return true;
}
return false;
}
int solve(string A,string B){
int l;
int f=-1;
for(int i=0;i<A.size();i++){
if(A[i]!=B[i] && i!=f){
v.push_back(i);
}
}
if(v.size()%2==0){
l=v.size();
}
else{
l=v.size()-1;
f=v.back();
}
for(int i=0;i<l-1;i+=2){
swap(A[v[i]],A[v[i+1]]);
v.erase(v.begin()+i);
v.erase(v.begin()+i);
swa++;
}
if(A!=B){
solve(A,B);
}
return swa;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int size,q;
cin>>size>>q;
int aa,bb;
string a,b;
cin>>a>>b;
while(q--){
cin>>aa>>bb;
string aaa=a.substr(aa,bb);
string bbb=b.substr(aa,bb);
if(chars(aaa,bbb)){
cout<<-1<<'\n';
continue;
}
cout<<solve(aaa,bbb);
swa=0;
v.clear();
cout<<'\n';
}
}