Submission #1247063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247063		mightyrock	Mutating DNA (IOI21_dna)	C++20	100 / 100	77 ms	19052 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define vp vector<pi>
#define fi first
#define se second
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define vvl vector<vl>

using namespace std;

vi A,B;

struct node {
    node *l = nullptr,*r = nullptr, *par = nullptr;
    int dif[3][3] = {{0,0,0},{0,0,0},{0,0,0}}; //dif[i][j] = num of indices where a has i and b has i+j
    node() {}
    node(int i, int j, node *par) : par(par) {
        dif[i][j] = 1;
    }
    node(node *l, node *r, node *par) : l(l), r(r), par(par) {
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j) {
                dif[i][j] = l->dif[i][j] + r->dif[i][j];
            }
        }
    };
};

node neu = node();

node * init2(node *par, int L, int R) {
    if (R - L == 1) return new node(A[L], B[L], par);
    int mid = (L+R)/2; 
    node *chL = init2(nullptr, L, mid);
    node *chR = init2(nullptr, mid, R);
    node *res = new node(chL, chR, par);
    chL->par = res;
    chR->par = res;
    return res;
}

int res[3][3];
void query2(node *cur, int L, int R, int qL, int qR) {
    if (qR <= L || R <= qL) return;
    if (qL <= L && R <= qR) {
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j) res[i][j] += cur->dif[i][j];
        }
        return;
    }
    int mid = (L+R)/2;
    query2(cur->l, L, mid, qL, qR);
    query2(cur->r, mid, R, qL, qR);
}
node *rt;
int n;
void init(string a, string b) {
    int q;
    n = a.size();
    for (int i=0; i<n; ++i) {
        if (a[i] == 'A') A.pb(0);
        if (a[i] == 'C') A.pb(1);
        if (a[i] == 'T') A.pb(2);
        if (b[i] == 'A') B.pb(0);
        if (b[i] == 'C') B.pb(1);
        if (b[i] == 'T') B.pb(2);
    }
    rt = init2(nullptr, 0, n);
}

int get_distance(int x, int y) {
    for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) res[i][j] = 0;
    query2(rt, 0, n, x, y+1);
    int ans = 0;
    for (int i=0; i<3; ++i) {
        for (int j=0; j<3; ++j) {
            if (i==j) continue;
            int curmin = min(res[i][j], res[j][i]);
            res[i][j] -= curmin;
            res[j][i] -= curmin;
            ans += curmin;
        }
    }
    if (res[0][1] != res[1][2] || res[1][2] != res[2][0] || res[0][2] != res[1][0] || res[2][1] != res[1][0]) {
        return -1;
    }
    ans += 2*(res[0][1] + res[0][2]);
    return ans;
}

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