# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1240919 | bornag | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define X first
#define Y second
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
const ll MOD = 1e9 + 7;
const ll BASE = 32;
const int MAXN = 2e5 + 7;
int prefa[MAXN][5], prefb[MAXN][5], same[MAXN];
int n;
void init(string a, string b) {
n = len(a);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++)
prefa[i][j] = prefa[i - 1][j], prefb[i][j] = prefb[i - 1][j];
char let[] = {'A', 'T', 'C'};
for(int j = 0; j < 3; j++) {
if(a[i - 1] == let[j])
prefa[i][j]++;
if(b[i - 1] == let[j])
prefb[i][j]++;
}
same[i] = same[i - 1] + (a[i - 1] != b[i - 1]);
}
}
int ceil(int a) {
return a / 2 + (a % 2);
}
int get_distance(int x, int y) {
swap(x, y);
for(int j = 0; j < 3; j++)
if(prefa[x + 1][j] - prefa[y][j] != prefb[x + 1][j] - prefb[y][j])
return -1;
return ceil(same[x + 1] - same[y]);
}
int main() {
init("ATACAT", "ACTATA");
cout << get_distance(1, 3) << '\n';
}