| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 566891 | pawned | 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 <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
void init(std::string a, std::string b) {
int N = n;
int K = q;
int type1[N];
int type2[N];
for (int i = 0; i < N; i++) {
if (a[i] == 'A')
type1[i] = 0;
else if (a[i] == 'C')
type1[i] = 1;
else
type1[i] = 2;
if (b[i] == 'A')
type2[i] = 0;
else if (b[i] == 'C')
type2[i] = 1;
else
type2[i] = 2;
}
int counts1[N + 1][3];
int counts2[N + 1][3];
for (int i = 0; i < 3; i++) {
counts1[0][i] = 0;
counts2[0][i] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) {
counts1[i][j] = counts1[i - 1][j];
counts2[i][j] = counts2[i - 1][j];
}
counts1[i][type1[i - 1]]++;
counts2[i][type2[i - 1]]++;
}
/*
cout<<"counts1: "<<endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j <= N; j++) {
cout<<counts1[j][i]<<" ";
}
cout<<endl;
}
cout<<endl;
*/
int pfs[N + 1][3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
pfs[0][i][j] = 0;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
pfs[i][j][k] = pfs[i - 1][j][k];
}
}
pfs[i][type1[i - 1]][type2[i - 1]]++;
}
}
int get_distance(int x, int y) {
int l, r;
l = x;
r = y;
bool works = true;
for (int j = 0; j < 3; j++) {
if ((counts1[r + 1][j] - counts1[l][j]) != (counts2[r + 1][j] - counts2[l][j]))
works = false;
}
if (!works) {
cout<<-1<<endl;
return 0;
}
int vals[3][3];
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
vals[j][k] = pfs[r + 1][j][k] - pfs[l][j][k];
}
}
int total = vals[0][0] + vals[1][1] + vals[1][2];
int x1 = min(vals[0][1], vals[1][0]);
total += x1;
vals[0][1] -= x1;
vals[1][0] -= x1;
int x2 = min(vals[0][2], vals[2][0]);
total += x2;
vals[0][2] -= x2;
vals[2][0] -= x2;
int x3 = min(vals[1][2], vals[2][1]);
total += x3;
vals[1][2] -= x3;
vals[2][1] -= x3;
total += 2 * max(vals[0][1], vals[1][0]);
cout<<total<<endl;
return 0;
}