| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1237656 | fauntleroy | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
#define int long long
using namespace std;
const int mxn = 100000;
int pref[mxn + 1][3][3];
int get(char c) {
if (c == 'A')
return 0;
if (c == 'T')
return 1;
return 2;
}
void init(string a, string b) {
int n = a.size();
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
pref[0][x][y] = 0;
pref[0][get(a[0])][get(b[0])] = 1;
for (int i = 1; i < n; ++i) {
int u = get(a[i]), v = get(b[i]);
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
pref[i][x][y] = pref[i - 1][x][y];
pref[i][u][v]++;
}
}
int get_distance(int l, int r) {
int cnt[3][3];
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
cnt[x][y] = pref[r][x][y] - (l > 0 ? pref[l - 1][x][y] : 0);
for (int c = 0; c < 3; ++c) {
int o = cnt[c][0] + cnt[c][1] + cnt[c][2];
int i = cnt[0][c] + cnt[1][c] + cnt[2][c];
if (o != i)
return -1;
}
int ans = 0;
for (int x = 0; x < 3; ++x) {
for (int y = x + 1; y < 3; ++y) {
int d = min(cnt[x][y], cnt[y][x]);
ans += d;
cnt[x][y] -= d;
cnt[y][x] -= d;
}
}
int k = 0;
for (int x = 0; x < 3; ++x)
for (int y = 0; y < 3; ++y)
k += cnt[x][y];
ans += 2 * k / 3;
return ans;
}