Submission #784010

#	Time	Username	Problem	Language	Result	Execution time	Memory
784010		Matblube	Mutating DNA (IOI21_dna)	C++17	43 / 100	1584 ms	2448 KiB

dna

#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, ll 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;
    adn left = queryStA(l, r, 2*i+1, tl, mid);
    adn right = queryStA(l, r, 2*i+2, mid+1, tr);
    return left + right;
}

adn queryStB(ll l, ll r, ll i, ll tl, ll 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;
    adn left = queryStB(l, r, 2*i+1, tl, mid);
    adn 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;
}

Compilation message (stderr)

dna.cpp: In member function 'adn adn::operator+(adn)':
dna.cpp:35:5: warning: no return statement in function returning non-void [-Wreturn-type]
   35 |     }
      |     ^

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16