| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 758181 | JANCARAPAN | 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 fi first
#define se second
#define sz(a) (long long) a.size()
//#define endl '\n'
const long long INF = 1e18, MOD = 1e9+7;
vector<vector<int>> pref;
int get_distance(int l, int r) {
int aa = pref[r + 1][0] - pref[l][0], ab = pref[r + 1][1] - pref[l][1], ac = pref[r + 1][2] - pref[l][2];
int ba = pref[r + 1][3] - pref[l][3], bb = pref[r + 1][4] - pref[l][4], bc = pref[r + 1][5] - pref[l][5];
int ca = pref[r + 1][6] - pref[l][6], cb = pref[r + 1][7] - pref[l][7], cc = pref[r + 1][8] - pref[l][8];
if (ab + ac != ba + ca or ba + bc != ab + cb or ca + cb != ac + bc) return -1;
int x = min(ab, ba), y = min(ac, ca), z = min(bc, cb);
int ans = x + y + z;
ab -= x; ba -= x;
ac -= y; ca -= y;
bc -= z; cb -= z;
ans += max(0, ab + ba + ac + ca + bc + cb - 1);
return ans;
}
void init(string a, string b) {
int n = a.size();
for (int i = 0; i < n; i++) {
if (a[i] == 'T') a[i] = 'B';
if (b[i] == 'T') b[i] = 'B';
}
pref = vector<vector<int>> (n + 1, vector<int>(9)); // 0 = A-A, 1 = A-B, 2 = A-C, 3 = B-B...
for (int i = 0; i < n; i++) {
pref[i + 1][3*(a[i]-'A')+(b[i]-'A')] += 1;
for (int j = 0; j < 9; j++) {
pref[i + 1][j] += pref[i][j];
}
}
cout << get_distance(1, 3) << endl;
cout << get_distance(4, 5) << endl;
cout << get_distance(3, 5) << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
init("ATACAT", "ACTATA");
}
return 0;
}