# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1240970 | gkos5678 | Mutating DNA (IOI21_dna) | C++20 | 21 ms | 5776 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
const int maxn = 1e5 + 5;
int n;
int pf[3][3][maxn], ar[3][3], kk[2][3];
int f(char c){
if (c == 'A') return 0;
if (c == 'C') return 1;
return 2;
}
void init(string a, string b){
n = a.size();
a = '$' + a;
b = '$' + b;
for (int i = 1; i <= n; i++){
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
pf[j][k][i] = pf[j][k][i - 1];
}
}
int c1 = f(a[i]), c2 = f(b[i]);
pf[c1][c2][i]++;
}
}
int get_distance(int x, int y){
x++, y++;
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
ar[j][k] = pf[j][k][y] - pf[j][k][x - 1];
kk[j][0] += ar[j][k];
kk[k][1] += ar[j][k];
}
}
for (int i = 0; i < 3; i++){
if (kk[i][0] != kk[i][1]) return -1;
}
int ret = 0;
for (int j = 0; j < 2; j++){
for (int k = j + 1; k < 3; k++){
int mn = min(ar[j][k], ar[k][j]);
ar[j][k] -= mn, ar[k][j] -= mn;
ret += mn;
}
}
int sm = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
sm += ar[i][j];
ret += sm * 2 / 3;
return ret;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |