# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
439308 | 4fecta | 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;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)
const int MN = 100005;
int n, ac[MN], ca[MN], ct[MN], tc[MN], ta[MN], at[MN];
void init(string a, string b) {
n = a.size();
for (int i = 1; i <= n; i++) {
char f = a[i - 1], s = b[i - 1];
if (f == 'A' && s == 'C') ac[i]++;
if (f == 'C' && s == 'A') ca[i]++;
if (f == 'C' && s == 'T') ct[i]++;
if (f == 'T' && s == 'C') tc[i]++;
if (f == 'T' && s == 'A') ta[i]++;
if (f == 'A' && s == 'T') at[i]++;
ac[i] += ac[i - 1];
ca[i] += ca[i - 1];
ct[i] += ct[i - 1];
tc[i] += tc[i - 1];
ta[i] += ta[i - 1];
at[i] += at[i - 1];
}
}
int get_distance(int x, int y) {
x++, y++;
int AC = ac[y] - ac[x - 1];
int CA = ca[y] - ca[x - 1];
int CT = ct[y] - ct[x - 1];
int TC = tc[y] - tc[x - 1];
int TA = ta[y] - ta[x - 1];
int AT = at[y] - at[x - 1];
int m1 = min(AC, CA), m2 = min(CT, TC), m3 = min(TA, AT);
int ans = m1 + m2 + m3;
AC -= m1, CA -= m1, CT -= m2, TC -= m2, TA -= m3, AT -= m3;
if (AC != CT || CT != TA) return -1;
if (CA != TC || TC != AT) return -1;
ans += (AC + CA) * 2;
return ans;
}
int32_t main() {
boost();
return 0;
}