| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1297402 | baodat | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
const int N = 1e5 + 5;
int prefa_a[N], prefa_c[N], prefa_t[N];
int prefb_a[N], prefb_c[N], prefb_t[N];
int diff[N][3][3];
string a, b;
int n;
int get_id(char c){
if(c == 'A') return 0;
if(c == 'C') return 1;
return 2;
}
void init(string a, string b){
a = __a;
b = __b;
n = a.size();
a = ' ' + a;
b = ' ' + b;
FOR(i, 1, n){
prefa_a[i] = prefa_a[i - 1] + (a[i] == 'A');
prefa_c[i] = prefa_c[i - 1] + (a[i] == 'C');
prefa_t[i] = prefa_t[i - 1] + (a[i] == 'T');
prefb_a[i] = prefb_a[i - 1] + (b[i] == 'A');
prefb_c[i] = prefb_c[i - 1] + (b[i] == 'C');
prefb_t[i] = prefb_t[i - 1] + (b[i] == 'T');
int idx1 = get_id(a[i]), idx2 = get_id(b[i]);
FOR(id1, 0, 2)FOR(id2, 0, 2){
diff[i][id1][id2] = diff[i - 1][id1][id2];
}
diff[i][idx1][idx2] += 1;
}
}
int geta_a(int l, int r){
return prefa_a[r] - prefa_a[l - 1];
}
int geta_c(int l, int r){
return prefa_c[r] - prefa_c[l - 1];
}
int geta_t(int l, int r){
return prefa_t[r] - prefa_t[l - 1];
}
int getb_a(int l, int r){
return prefb_a[r] - prefb_a[l - 1];
}
int getb_c(int l, int r){
return prefb_c[r] - prefb_c[l - 1];
}
int getb_t(int l, int r){
return prefb_t[r] - prefb_t[l - 1];
}
//0 -> A, 1 -> C, 2 -> T
int get_distance(int l, int r){
++l;
++r;
if(geta_a(l, r) == getb_a(l, r) &&
geta_c(l, r) == getb_c(l, r) &&
geta_t(l, r) == getb_t(l, r)){
int ac = diff[r][0][1] - diff[l - 1][0][1];
int at = diff[r][0][2] - diff[l - 1][0][2];
int ca = diff[r][1][0] - diff[l - 1][1][0];
int ct = diff[r][1][2] - diff[l - 1][1][2];
int ta = diff[r][2][0] - diff[l - 1][2][0];
int tc = diff[r][2][1] - diff[l - 1][2][1];
int ans = 0;
int t;
//mis of A T
t = min(at, ta);
ans += t;
at -= t;
ta -= t;
//mis of A C
t = min(ac, ca);
ans += t;
ac -= t;
ca -= t;
// mis of C T
t = min(tc, ct);
ans += t;
tc -= t;
ct -= t;
//cerr << "AFTER 1 CYCLE:\n" << at << " " << ta << " " << ac << " " << ca << " " << tc << " " << ct << "\n";
//now AC - CT - TA, take 2
ans += 2 * (ac + ct + ta) / 3;
//AT - TC - CA
ans += 2 * (at + tc + ca) / 3;
//CT - TA - AC
ans += 2 * (ct + ta + ac) / 3;
return ans;
}
else return -1;
}/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string __a, __b;
cin >> __a >> __b;
init(__a, __b);
int q;
int case_cnt = 1;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
cout << "Case " << case_cnt++ << ": " << get_distance(l, r) << "\n";
}
return 0;
}*/