| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 784008 | Matblube | 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 <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
#define fr(i, x) for(ll i=0 ; i<x ; i++)
#define fra(x, v) for(auto x:v)
#define fra1(x,v) for(auto &x:v)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pb(x) push_back(x)
#define sz(x) (ll) x.size()
#define F first
#define S second
const ll maxN=1e5;
struct adn{
ll a, c, t;
adn operator+(adn xd){
a += xd.a;
c += xd.c;
t += xd.t;
}
};
string n, m;
adn stA[4*maxN];
adn stB[4*maxN];
ll stDif[4*maxN];
void initStDif(ll i, ll l, ll r){
if(l == r){
stDif[i] = (n[l] != m[l]);
return;
}
ll mid = (l + r)/2;
initStDif(2*i+1, l, mid);
initStDif(2*i+2, mid+1, r);
stDif[i] = stDif[2*i+1] + stDif[2*i+2];
}
ll queryStDif(ll l, ll r, ll i, ll tl, ll tr){
if(tl >= l && tr <= r){
return stDif[i];
}
if(tl > r or tr < l){
return 0;
}
ll mid = (tl + tr) / 2;
ll left = queryStDif(l, r, 2*i+1, tl, mid);
ll right = queryStDif(l, r, 2*i+2, mid+1, tr);
return left + right;
}
void initStA(ll i, ll l, ll r){
if(l == r){
stA[i] = {(n[l] == 'A'), (n[l] == 'C'), (n[l] == 'T')};
return;
}
ll mid = (l+r)/2;
initStA(2*i+1, l, mid);
initStA(2*i+2, mid+1, r);
stA[i] = stA[2*i+1] + stA[2*i+2];
}
void initStB(ll i, ll l, ll r){
if(l == r){
stB[i] = {(m[l] == 'A'), (m[l] == 'C'), (m[l] == 'T')};
return;
}
ll mid = (l+r)/2;
initStB(2*i+1, l, mid);
initStB(2*i+2, mid+1, r);
stB[i] = stB[2*i+1] + stB[2*i+2];
}
adn queryStA(ll l, ll r, ll i, ll tl, tr){
if(tl >= l && tr <= r){
return stA[i];
}
if(tr < l or tl > r){
adn xd = {0, 0, 0};
return xd;
}
ll mid = (tl+tr)/2;
ll left = queryStA(l, r, 2*i+1, tl, mid);
ll right = queryStA(l, r, 2*i+2, mid+1, tr);
return left + right;
}
adn queryStB(ll l, ll r, ll i, ll tl, tr){
if(tl >= l && tr <= r){
return stB[i];
}
if(tr < l or tl > r){
adn xd = {0, 0, 0};
return xd;
}
ll mid = (tl+tr)/2;
ll left = queryStB(l, r, 2*i+1, tl, mid);
ll right = queryStB(l, r, 2*i+2, mid+1, tr);
return left + right;
}
void init(std::string a, std::string b) {
n=a; m=b;
initStA(0, 0, sz(a)-1);
initStB(0, 0, sz(b)-1);
initStDif(0, 0, min(sz(a), sz(b))-1);
}
int get_distance(int x, int y) {
// xdpro
map<char, ll>uwu1, uwu2;
for(ll i=x ; i<=y ; i++){
uwu1[n[i]]++;
uwu2[m[i]]++;
}
fra(pro, uwu1){
if(pro.second!=uwu2[pro.first]){
return -1;
}
}
fra(pro, uwu2){
if(pro.second!=uwu1[pro.first]){
return -1;
}
}
ll cc=0;
for(ll i=x ; i<=y ; i++){
if(n[i]!=m[i]) cc++;
}
return (cc+1)/2;
}