| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298219 | tit_manh | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
/*
author : TIT_manh
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <numeric>
#include <functional>
#include <cassert>
#include <sstream>
#include <climits>
#define ll long long
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FOD(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define endl "\n"
using namespace std;
const int maxn = 1e5 + 5;
int n, pre1[3][maxn], pre2[3][maxn];
int p1[maxn]; // A-T
int p2[maxn]; // T-A
int p3[maxn]; // T-C
int p4[maxn]; // C-T
int p5[maxn]; // A-C
int p6[maxn]; // C-A
void init(string a, string b) {
n = a.size();
FOR(i,0,n-1) {
if (i != 0) p[i] = p[i - 1];
if (a[i] == 'A' && b[i] == 'T') p1[i] = 1;
if (a[i] == 'T' && b[i] == 'A') p2[i] = 1;
if (a[i] == 'T' && b[i] == 'C') p3[i] = 1;
if (a[i] == 'C' && b[i] == 'T') p4[i] = 1;
if (a[i] == 'A' && b[i] == 'C') p5[i] = 1;
if (a[i] == 'C' && b[i] == 'A') p6[i] = 1;
if (a[i] == 'A') {
pre1[0][i] = 1;
}
if (a[i] == 'C') {
pre1[1][i] = 1;
}
if (a[i] == 'T') {
pre1[2][i] = 1;
}
if (b[i] == 'A') {
pre2[0][i] = 1;
}
if (b[i] == 'C') {
pre2[1][i] = 1;
}
if (b[i] == 'T') {
pre2[2][i] = 1;
}
if (i != 0) {
pre1[0][i] += pre1[0][i - 1];
pre1[1][i] += pre1[1][i - 1];
pre1[2][i] += pre1[2][i - 1];
pre2[0][i] += pre2[0][i - 1];
pre2[1][i] += pre2[1][i - 1];
pre2[2][i] += pre2[2][i - 1];
p1[i] += p1[i - 1];
p2[i] += p2[i - 1];
p3[i] += p3[i - 1];
p4[i] += p4[i - 1];
p5[i] += p5[i - 1];
p6[i] += p6[i - 1];
}
}
}
int get_distance(int x, int y) {
// differ : A-T, C-T, A-C, T-A, T-C, C-A
// ACAT
// TTCA
FOR(i,0,2) {
if (x == 0) {
if (pre1[i][y] != pre2[i][y]) return -1;
}
else if (pre1[i][y] - pre1[i][x - 1] != pre2[i][y] - pre2[i][x - 1]) return -1;
}
int t1, t2, t3, t4, t5, t6;
if (x == 0) {
t1 = p1[y];
t2 = p2[y];
t3 = p3[y];
t4 = p4[y];
t5 = p5[y];
t6 = p6[y];
}
else {
t1 = p1[y] - p1[x - 1];
t2 = p2[y] - p2[x - 1];
t3 = p3[y] - p3[x - 1];
t4 = p4[y] - p4[x - 1];
t5 = p5[y] - p5[x - 1];
t6 = p6[y] - p6[x - 1];
}
int res = 0;
if (t1 < t2) swap(t1, t2);
if (t3 < t4) swap(t3, t4);
if (t5 < t6) swap(t5, t6);
res = t2 + t4 + t6;
t1 -= t2; t3 -= t4; t5 -= t6;
if (t1 > 0) res += 2;
return res;
}