Submission #924872

#	Time	Username	Problem	Language	Result	Execution time	Memory
924872		Programmer123	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	8580 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

int N;
int *anumA, *anumT, *anumC;
int *bnumA, *bnumT, *bnumC;
int *diff;
int *dats, *dacs, *dtas, *dtcs, *dcas, *dcts;
std::string A, B;

void init(std::string _a, std::string _b) {
    A = std::move(_a);
    B = std::move(_b);
    N = A.size();
    for (auto x: {&anumA, &anumT, &anumC, &bnumA, &bnumT, &bnumC, &diff, &dats, &dacs, &dtas, &dtcs, &dcas, &dcts}) {
        *x = new int[N];
    }
    anumA[0] = A[0] == 'A';
    anumT[0] = A[0] == 'T';
    anumC[0] = A[0] == 'C';
    bnumA[0] = B[0] == 'A';
    bnumT[0] = B[0] == 'T';
    bnumC[0] = B[0] == 'C';
    diff[0] = A[0] != B[0];

    dats[0] = (A[0] == 'A' && B[0] == 'T');
    dacs[0] = (A[0] == 'A' && B[0] == 'C');
    dtas[0] = (A[0] == 'T' && B[0] == 'A');
    dtcs[0] = (A[0] == 'T' && B[0] == 'C');
    dcas[0] = (A[0] == 'C' && B[0] == 'A');
    dcts[0] = (A[0] == 'C' && B[0] == 'T');

    for (int i = 1; i < N; ++i) {
        anumA[i] = anumA[i - 1] + (A[i] == 'A');
        anumT[i] = anumT[i - 1] + (A[i] == 'T');
        anumC[i] = anumC[i - 1] + (A[i] == 'C');

        bnumA[i] = bnumA[i - 1] + (B[i] == 'A');
        bnumT[i] = bnumT[i - 1] + (B[i] == 'T');
        bnumC[i] = bnumC[i - 1] + (B[i] == 'C');

        diff[i] = diff[i - 1] + (A[i] != B[i]);

        dats[i] = dats[i - 1] + (A[i] == 'A' && B[i] == 'T');
        dacs[i] = dacs[i - 1] + (A[i] == 'A' && B[i] == 'C');
        dtas[i] = dtas[i - 1] + (A[i] == 'T' && B[i] == 'A');
        dtcs[i] = dtcs[i - 1] + (A[i] == 'T' && B[i] == 'C');
        dcas[i] = dcas[i - 1] + (A[i] == 'C' && B[i] == 'A');
        dcts[i] = dcts[i - 1] + (A[i] == 'C' && B[i] == 'T');
    }
}

int num(int *data, int l, int r) {
    int x = data[r];
    if (l) x -= data[l - 1];
    return x;
}

int get_distance(int x, int y) {
    int aa = num(anumA, x, y);
    int ba = num(bnumA, x, y);
    int at = num(anumT, x, y);
    int bt = num(bnumT, x, y);
    int ac = num(anumC, x, y);
    int bc = num(bnumC, x, y);
    if (aa != ba || at != bt || ac != bc) return -1;
    if (y - x <= 2) {//Subtask 1
        int d = 0;
        for (int i = x; i <= y; ++i) {
            d += A[i] != B[i];
        }
        return (d + 1) / 2;
    }
    if ((ac == 0 && bc == 0) || (aa == 0 && ba == 0) || (at == 0 && bt == 0)) {
        return num(diff, x, y) / 2;
    }
    int dac = num(dacs, x, y);
    int dat = num(dats, x, y);
    int dta = num(dtas, x, y);
    int dtc = num(dtcs, x, y);
    int dca = num(dcas, x, y);
    int dct = num(dcts, x, y);
    int groupA = dac - dca;
    assert(groupA == dta - dat);
    assert(groupA == dct - dtc);
    int ans = 0;
    if (groupA > 0) {
        ans = 2 * groupA;
        dac -= groupA;
        dct -= groupA;
        dta -= groupA;
    } else if (groupA < 0) {
        ans = -2 * groupA;
        dca += groupA;
        dtc += groupA;
        dat += groupA;
    }
    assert(dac == dca);
    assert(dat == dta);
    assert(dct == dtc);
    ans += dac + dat + dct;
    return ans;
}

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