Submission #924868

#	Time	Username	Problem	Language	Result	Execution time	Memory
924868		Programmer123	Mutating DNA (IOI21_dna)	C++17	56 / 100	29 ms	6008 KiB

dna

#include "dna.h"

int N;
int *anumA, *anumT, *anumC;
int *bnumA, *bnumT, *bnumC;
int *diff;
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}) {
        *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];
    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]);
    }
}

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;
    }
    return 0;
}

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