# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
567955 | sdfsdfsddf | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int max_n = 10e5+7;
int literki1[max_n][3]{};
int literki2[max_n][3]{};
int do_zamiany[max_n]{};
void init(string s, string x){
int a = 0, c= 0, t =0;
//a = 0 b = 1 c = 2
int lenggg = s.length();
for(int i = 0; i < lenggg;i++){
literki1[i][0] = a;
literki1[i][1] = c;
literki1[i][2] = t;
if(s[i] == 'A'){
a++;
literki1[i][0] += 1;
}
else if(s[i] == 'C'){
c++;
literki1[i][1] += 1;
}
else{
t++;
literki1[i][2] += 1;
}
}
a = 0;
c = 0;
t = 0;
for(int i = 0; i < lenggg;i++){
literki2[i][0] = a;
literki2[i][1] = c;
literki2[i][2] = t;
if(x[i] == 'A'){
a++;
literki2[i][0] += 1;
}
else if(x[i] == 'C'){
c++;
literki2[i][1] += 1;
}
else{
t++;
literki2[i][2] += 1;
}
}
int ile_zmienic = 0;
for(int i = 0; i < lenggg;i++){
if(s[i] != x[i])
ile_zmienic++;
do_zamiany[i] = ile_zmienic;
}
}
int get_distance(int x, int y){
int a1 = literki1[y][0]-literki1[x][0];
int c1 = literki1[y][1]-literki1[x][1];
int t1 = literki1[y][2]-literki1[x][2];
int a2 = literki1[y][0]-literki1[x][0];
int c2 = literki1[y][1]-literki1[x][1];
int t2 = literki1[y][2]-literki1[x][2];
if(a1 == a2 && c1 == c2 && t1 == t2){
int wyjscie = (do_zamiany[y]-do_zamiany[x]+1)/2;
return wyjscie;
}
else{
return -1;
}
return 0;
}
int main(){
int n,q;
cin >> n >> q;
string a,b;
cin >> a >> b;
init(a,b);
for(int i = 0; i < q; i++){
int x,y;
cin >> x >> y;
cout << get_distance(x,y) << '\n';
}
}