# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527578 | vivaan_gupta | 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 "dna.h"
// #include <iostream>
using namespace std;
const int N = 1e5 + 5;
int pre[N];
int n;
int ones[N], ones2[N];
void init(std::string a, std::string b) {
n = a.size();
for(int i = 0;i < n;i++){
int cnt = (a[i] != b[i]);
pre[i] = cnt;
ones[i] = (a[i] ==1)
ones2[i] = (b[i] == 1);
if(i > 0) {
pre[i] += pre[i-1];
ones[i] += ones[i-1];
ones2[i] += ones2[i-1];
}
}
}
int get_distance(int x, int y) {
int A = ones[y], B = ones2[y];
if(x > 0) A -= ones[x - 1], B -= ones2[x - 1];
if(A != B){
return -1;
}
int sum = pre[y];
if(x > 0) sum -= pre[x - 1];
return (sum / 2);
}