| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 567955 | sdfsdfsddf | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
}